문제 설명
Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.
- 1 + 2 + 3 + 4 + 5 = 15
- 4 + 5 + 6 = 15
- 7 + 8 = 15
- 15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.
제한 사항
- n은 10,000 이하의 자연수 입니다.
입출력 예
| n | result |
|---|---|
| 15 | 4 |
풀이
function solution(n) {
var answer = 0;
for(let i=1; i<=n; i++) {
if( n%i == 0 && i%2 ==1 )
answer++
}
return answer;
}풀이 설명
1️⃣
연속하는 수의 합이 n이 되야 한다.
임의의 자연수 a부터 k번 연속한 자연수의 합
a + (a+1) + (a+2) ... (a+k-1)
식으로 정리하면
k{a+(a+k-1)}/2
얘가 주어진 수 n이 되야 하므로
k(2a+k-1)/2 = n
2️⃣
여기서 a가 임의의 자연수라고 했으므로 a가 자연수가 될 조건만 충족하면
a부터 연속한 수를 k번 더했을 때 자연수 n이 된다
a에 대한 식으로 바꾸면
a = n/k + (1-k)/2가 되고, a가 자연수가 되기 위한 조건으로
1) n/k가 자연수가 되기 위해서 k는 n의 약수여야한다.
2) (1-k)/2가 정수가 되기 위해서(이러면 음수나 0이 나올수도 있을텐데?) k는 홀수여야 한다.
(k는 횟수이므로 무조건 자연수이다)
3️⃣
풀이 속 if문의 i는 덧셈을 시작하는 자연수(a)가 아닌,
연속한 수의 갯수(k)를 의미하고(1 =< k <= n),
num에 나누어 떨어져야하며(num의 약수)(1번 조건),
i%2 == 1(홀수)여야 한다(2번 조건).
k의 조건이 만족하게 되면 임의의 자연수 a로부터 k번 연속하는 수를 더해서 n이 된다.
(a가 어떤 수인지는 구할 필요 없음. 조건에 충족하는 경우의 수만 다 더하면 되기 때문)
하나의 num 안에서 k(횟수)가 중복되는 경우는 없기 때문에
조건을 만족하는 k의 갯수가 결국 답이 된다.
4️⃣
<결론으로 알 수 있는 규칙>
i가 n의 약수이면서 홀수이면 i번만큼 연속하는 수의 합이 n이 될 수 있다.
5️⃣
예외의 발견
65의 약수: 1, 5, 13, 65
13번 연속하는 수: -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
자연수가 아닌 음수가 발생하는 경우가 있다.
5 * 13 = 65의 경우, 13의 반보다 5가 작기 때문에 음수가 발생한다.
만약 구해야 하는 값이 방법의 수가 아니라 방법들의 숫자 배열을 구해야 한다면 위 풀이 방법으로는 틀리게 된다.
그럴 땐 13/2 > 5일 경우에 대한 조건을 추가해서 해결해야 할 것 같다.
