문제 설명
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문을 통해 1 + 2 + 3 + 4 + 5를 구하면 다음 반복자는 6을 가리키게 될 것인데, 이때 반복문을 종료하고 다시 1이 아닌 다른 수를 시작으로 반복문이 진입하게끔 만들어야 한다.
이때 생각한 방법은 두 가지인데, 첫 번째는 재귀였다.
숫자들의 합을 sum이라고 할 때, sum ≥ n 을 만족하면 탈출하는 조건으로 재귀를 돌리는 것이다.
class Solution {
int answer = 1; // 자기 자신
public int solution(int n) {
for (int i = 1; i < n; i++) {
recursive(n, i, 0);
}
return answer;
}
public void recursive(int n, int idx, int sum) {
if (sum >= n) {
if (sum == n) {
answer++;
}
return;
}
recursive(n, idx + 1, sum + idx);
}
}위와 같은 코드로 접근하였으며 어렵지 않게 테스트를 통과할 수 있었다.
두 번째 방법은 for문 내에서 while문을 동작시키는 것이었다.
class Solution {
public int solution(int n) {
int answer = 1; // 자기 자신
for (int i = 1; i < n; i++) {
int tmp = i;
int sum = 0;
while (tmp != n) {
sum += tmp;
tmp++;
if (sum >= n) {
break;
}
}
if (sum == n) answer++;
}
return answer;
}
}위와 같은 코드로 풀어냈는데, 이 역시 어렵지 않게 테스트를 통과할 수 있었다.
재귀와 반복문 양쪽 모두 어렵지 않은 풀이과정이었지만, 문제 자체도 단순했기에 굳이 재귀를 써가며 푸는 것 보다는 while문을 통해 푸는 과정이 좀 더 나았지 않았나 생각한다.
