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 |
입출력 예#1
문제의 예시와 같습니다.
아래와 같이 연속된 숫자를 더해보면 n/2 부터는 더해도 의미가 없음을 알 수 있다.
1 + 2 + 3 + 4 + 5 = 15
2 + 3 + 4 + 5 + 6 = 20
3 + 4 + 5 + 6 = 18
4 + 5 + 6 = 15
5 + 6 + 7 = 18
6 + 7 + 8 = 21
7 + 8 = 15
여기서부턴 가망이 없음
8 + 9 = 17
9 + 10 = 19
10 + 11 = 21
11 + 12 = 23
12 + 13 = 25
13 + 14 = 27
14 + 15 = 29
15 = 15
그래서 이를 바탕으로 코드를 짜면 아래와 같다
function solution(n) {
let answer = 1; // n === n 일때
let num = 0;
for (let i = 1; i < n / 2; i++) {
for (let j = i; j < n / 2 + 1; j++) {
num += j;
if (num >= n) {
// 연속된 숫자를 더한 값이 n과 같으면 answer += 1
if (num === n) answer++;
// num이 n보다 크거나 같으면 num을 초기화하고 break
num = 0;
break;
}
}
}
return answer;
}
약수를 사용해 푼 경우
function expressions(num) {
var answer = 0;
for(var i=1; i<=num; i++) {
if (num%i == 0 && i%2 == 1)
answer++
}
return answer;
}
: 약수가 항상 홀수
ex) 15 : 1, 3, 5, 15
1+2+3+4+5 ➡️ 중간값 3 ➡️ 3x5
4+5+6 ➡️ 중간값 5 ➡️ 5x3
7+8 ➡️ 연속된 수 ➡️ 7+8 : 홀수인 경우 무조건 가능
15=15
중간값이 3, 중간값이 5, 연속된 수, n 이렇게 4개 ➡️ 홀수의 약수 개수와 같음
: 홀수의 연장선
ex) 30 : 1, 2, 3, 5, 6, 10, 15, 30
4 + 5 + 6 + 7 + 8 ➡️ 중간값 3의 연장 ➡️ 2x3x5
9 + 10 + 11 ➡️ 중간값 5의 연장 ➡️ 2x5x3
6+7+8+9 ➡️ 연속된 두 수의 연장 ➡️ 2x(7+8)
30
결과적으로 n의 홀수 약수 개수만 구해도 답과 같음