프로그래머스
숫자의 표현
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성
처음 해당 문제를 보았을 때 반복문을 사용해 해결하려고 했다.
하지만 연속된 수를 확인하고 어떤 숫자부터 연속된 숫자를 고르는 지 등을 생각하다보니 효율적이지 못하다는 생각을 했고 이를 점화식으로 만들면 어떨지 생각을 하게 되었다.
1~n까지의 숫자를 더한 값은 n(n+1)/2의 점화식이 나오는 것을 알았기 때문에 이를 응용하면 되겠다 싶었다.
시작 숫자를 s 숫자의 개수를 c라 할 때 s+(s+1)+(s+2)+...(s+c-1)=n의 식이 성립하고 이를 정리하면
1 ~ (s+c-1)까지 숫자의 합 - 1 ~ (s-1)까지 숫자의 합이기 때문에 c(2s+c-1)/2 = n의 식으로 정리된다.
이를 시작 숫자 s를 기준으로 정리 -> s = n/c+(1-c)/2
s는 자연수가 나와야 하기 때문에 c는 n의 약수이며 홀수여야 한다.
식이 정리되니 구현해야 할 코드가 효과적으로 줄어들었다.
코드
def solution(n):
answer = 0
for i in range(1,n+1,2):
if n%i==0:
answer+=1
return answer