규칙을 찾으려다가 약수를 이용하면 된다까지는 접근했으나 더 나아가지 못했다.
다른 사람 풀이 1
def solution(n):
answer = 0
for i in range(1, n+1):
sum = 0
for j in range(i, n+1):
sum += j
if sum == n:
answer += 1
elif sum > n:
break
return answer그냥 문제 그대로 구현만 해도 되는 문제였다. 하지만 맨 처음에는 dp인가 생각했고 그 다음에는 약수로 규칙을 구하려다 보니 단순 구현을 생각하지 못했다. 제한 사항에서 n은 10,000이하라고 되어있으니 단순 구현도 고려를 헀어야 했다.
다른 사람 풀이 2
def solution(n):
odd_divisors = [i for i in range(1, n+1) if n % i == 0 and i % 2 == 1]
return len(odd_divisors)홀수인 약수의 개수를 구하는 풀이이다. 이 풀이가 유효한 이유는
"주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다라는 정수론 정리가 있습니다."
예를 들어 생각해보도록 하겠습니다.
15를 예로 생각해보면
15의 홀수인 약수는 1,3,5,15가 있습니다.
1) 약수가 1
1로 인해 15는 연속하는 하나의 자연수, 15로 이루어져있음을 알 수 있습니다.
2) 약수가 3
3으로 인해 15는 5+5+5 의 합으로 표현되는 것을 알 수 있고 약간의 조작을 통해 4+5+6 이 되고 연속하는 자연수가 됩니다.
3) 약수가 5
5도 마찬가지로 3+3+3+3+3 즉, 1+2+3+4+5 로 표현이 가능합니다.
4) 약수가 15
15같은 경우는 위의 1) 2) 3) 과는 조금 예외적이다. 모든 홀수 2n+1는 n 과 n+1, 연속하는 두 수의 합으로 표현 할 수 있으므로
이 경우에는 7+8로 생각하면 될 듯 합니다.
출처: https://ssungkang.tistory.com/entry/%EC%88%AB%EC%9E%90%EC%9D%98-%ED%91%9C%ED%98%84%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2
