[프로그래머스/Lv2] 숫자의 표현

문제

자연수 n이 주어질 때, 이 자연수 n을 연속한 자연수들로 표현할 수 있는 방법의 수를 반환하는 함수를 만들어야 한다.

 

 

제한조건

1. n은 10000이하의 자연수이다.

 

 

코드

def solution(n):
    answer = 1
    end_num = int(n/2) + 1
    for f_num in range(1, end_num):
        sum = 0
        for num in range(f_num, end_num+1):
            if sum + num > n:
                break
            else:
                sum += num

            if sum == n:
                answer += 1
                break
    
    return answer

 

 

설명

보통의 경우 이 문제를 처음 보면 1부터 n까지 연속해서 더해 n이 되는 경우를 찾아볼 것이다.

그런데 잘 살펴보면 n/2부터는 그 뒤로 연속해서 더해봤자 n보다 무조건 커지게 되는 것을 알 수 있다.

즉, 1부터 n까지가 아니라 1부터 n/2까지만 연속해서 더해보면 된다는 것이다.

그 후에 자기자신인 1을 더해주면 원하는 정답이 나올것이다.

 

answer = 1
end_num = int(n/2) + 1

answer는 방법의 수를 나타낸다. 1인 이유는 자기자신을 무조건 포함하기 때문.

end_num은 반복의 끝수를 나타낸다.

 

for f_num in range(1, end_num):
	sum = 0

가장 바깥쪽의 반복문이다.

1부터 end_num까지의 수들을 꺼내어 반복한다.

sum은 연속으로 더했을 때의 누적합을 나타낸다.

 

for num in range(f_num, end_num+1):
	if sum + num > n:
		break
	else:
		sum += num

안쪽의 반복문이다.

바깥쪽 반복문에서 넘어온 f_num부터 end_num+1까지의 수들을 꺼내어 반복한다.

우선 현재 sum과 num을 더했을 때 n을 초과하는가를 판단한다.

초과해버리면 연산할 필요가 없으니 break해준다.

아니라면 sum에 num을 더해준다.

 

if sum == n:
	answer += 1
	break

현재 sum이 n과 같으면 answer에 1을 더해준다.

이후 연산은 필요없으니 break해준다.

 

return answer

반복문이 끝나면 계산된 answer를 반환한다.

 

 

이 문제는 찾아보면 쉽게 풀 수 있는 방법이 많이 있다.

n의 약수들 중 홀수의 수를 세어서 문제를 풀거나 다른 수학적 방법으로 문제를 푼 사람들이 많이 보였다.

나는 수학적 방법의 원리를 모르겠어서 가장 직관적인 방법으로 문제를 풀었다.