12924. 숫자의 표현를 풀고 문제를 푼 기록이다. 언어는 JS를 사용하였다.
12924. 숫자의 표현
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
문제의 예시와 같습니다.
풀이
처음 문제에 접근 했을 때 일단 for문을 하나 작성했다. 이 for문은 1부터 n까지 돌아가는 for문으로 시작점을 위한 for문이다.
그다음 내부에 for문을 하나 더 작성했는데 이 for문은 시작점부터 숫자를 하나씩 더해가면서 n과 같거나 클때까지 계속 합치고 비교하는 for문이다.
내부 for문에서 숫자를 더하고, 만약 sum값이 n보다 작다면 계속 더해가고, 만약 n과 같은 경우가 있다면 cnt(결과물)을 1 증가시켜 준뒤 break로 다음 숫자로 넘어간다. 그리고 sum보다 크면 해당 값은 더이상 진행할 필요가 없으니 break를 통해서 다음 시작점으로 진행할 수 있도록 해준다.
처음에 이렇게 작성하고 채점을 하면 정확성은 100% 다 맞는데, 효율성에서 1개가 시간초과가 나왔는데.. 효율성을 늘리려면 for문을 적게 돌거나 없애야 하는데.. for문을 없애는건 가능하지가 않을것 같아서 for문을 적게 돌 수 있는 방법을 생각해봤다.
일단 n 을 2로 나눈값을 올림처리하면 n 자체를 제외하고는 가능한 숫자가 없다. 예제로 나온 15로 생가하면 15/2 = 7.5가 되고, 이를 올림처리하면 8이 나온다. 8을 시작점으로 더하면 무조건 15가 넘기 때문에 시작점은 8보다 작을때까지만 돌면 된다.
내부 for문의 경우에는 8까지 더해야 하는데, 예제를 보면 15는 7 + 8 이 가능하다. 결국 내부 for문에서는 n/2를 올림처리한 값까지 돌도록 하였다.
다만 이렇게만 하면 n 숫자 자체를 더해지지 않으므로 마지막 cnt 값에 1을 더해서 리턴하도록 하였는데, 만약 n이 1이라면 1자체 1개만 가능하므로 n이 1인 경우에는 그냥 리턴해버렸다.
효율성을 맞춰서 작성하는게 꽤 까다롭다는것을 다시한번 느꼈다.
function solution(n) {
let cnt = 0;
if (n === 1) {
return 1;
}
for(let i = 1; i < Math.ceil(n / 2); i += 1) {
let sum = 0;
for(let j = i; j <= Math.ceil(n / 2); j += 1) {
sum += j
if (sum < n) {
continue;
} else if( sum === n) {
cnt += 1;
break;
} else {
break;
}
}
}
return cnt + 1;
}결과
채점 결과
정확성: 75.0
효율성: 25.0
합계: 100.0 / 100.0