문제 설명
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풀이
등차수열 합 공식 n(2a+(n-1)d)/2 을 이용해 풀어보았다.
-> 테스트 케이스는 다 맞았는데 효율성 테스트에서 통과하지 못했다.
function solution(n) {
var answer = 0;
for(let i=1;i<=n;i++){
for(let j=1;j<=n;j++){
if(j*(2*i + j-1)/2 === n){
answer++;
break;
}
}
}
return answer;
}효율성을 높이기 위해 방법을 찾아보니, 다음과 같은 성질이 있었다.
⭐️ 주어진 값의 1/2을 초과하는 값 중에서는 연속되는 합의 값이 나올 수 없다.
예를 들어 15의 경우, 15의 절반인 7.xx를 넘는 8부터는 연속되는 합의 값이 무조건 15를 넘는다. 따라서 값을 전부 살피지 않고 절반까지만 탐색하면 된다.
해당 성질을 적용해보았으나, 여전히 효율성 테스트를 통과하지 못했다.
function solution(n) {
var answer = 0;
for(let i=1;i<=parseInt(n/2);i++){
for(let j=1;j<=n;j++){
if(j*(2*i + j-1)/2 === n){
answer++;
break;
}
}
}
return ++answer;
}등차수열을 이용한 다른 풀이
항의 개수 = x, 첫째항 = a, 마지막항 = b 라고 할 때,
등차수열 합공식에 의해 x(a+b) / 2 = n 이다.
항의 개수 x는 b - a + 1 로 표현할 수 있으므로 (-a+b+1)(a+b) = 2n로 치환할 수 있다.
이를 b에 대한 방정식으로 풀어본다면 b(b+1) = 2n + a(a - 1) 즉, 연속된 곱의 합으로 나타낼 수 있다.
수학에서 연속된 수의 곱이 해당 답이 나오기 위해서는 제곱근 바로 이전 정수가 연속해서 곱이 안된다면 연속된 수의 곱으로 나타낼 수 없기 때문에, 해당조건만 검사하면 된다.
function solution(n) {
let count = 0;
for(let i = 1; i<=Math.floor(n/2); i++){
let b = Math.floor(Math.sqrt(2 * n + (i**2-i)));
if(b * (b+1) === 2 * n + (i**2-i)) count ++
}
return count + 1;
}새로운 성질을 이용한 풀이 ⭐️
function solution(n) {
let answer = 0;
for(let i = 0; i <= n; i++) {
if(n%i === 0 && i%2 === 1) answer++;
}
return answer;
}다음과 같은 공식이 존재한다고 한다.
"주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수와 주어진 수의 홀수인 약수 갯수는 같다."
ex. 15
15의 약수는 1, 3, 5, 15 이고 이 중 홀수는 4개이다.
- 약수 1 => 연속하는 1개 자연수의 합으로 표현 가능
15 = 15 - 약수 3 => 연속하는 3개 자연수의 합으로 표현 가능
15를 3으로 나눈값인 5로 표현할 수 있다.
5 + 5 + 5 = 15 => 3 + 4 + 5 = 15 - 약수 5 => 연속하는 5개 자연수의 합으로 표현 가능
15를 5로 나눈값인 3으로 표현할 수 있다.
3 + 3 + 3 + 3 + 3 = 15 => 1 + 2 + 3 + 4 + 5 = 15 - 약수 15 => 모든 홀수(2n+1)는 n과 n+1로 표현 가능
7 + 8 = 15
