문제 설명
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과 같다면 answer에 기록하고, 초과하면 해당 값부터 다시 더해나간다면 정답을 구할 수 있지 않을까? 라고 생각했다.
하지만, 당장 문제에서 제시된 예시를 맞출 수도 없는 접근법이라서 다른 방식으로 접근하기로 생각했다.
두 번째 접근
그냥 효율성을 생각하기보다는 막연하게 떠오르는 방식을 구현하는 건 어떨까라고 생각했다(요약하면 완전탐색). 1부터 수를 하나 고정시켜 놓고 그 수에 1을 더한 수부터 계속 더해나가면서 n을 초과하거나 같을 때 특정 처리를 해 주면 될 것 같다는 생각이 들었다.
풀이
def solution(n):
answer = 1
for i in range(1, n // 2 + 1):
sum = i
for j in range(i + 1, n // 2 + 2):
sum += j
if sum > n:
break
elif sum == n:
answer += 1
break
return answer해결 과정
전체적인 흐름은 1 + 2 + 3 + ... 해서 n이 되는지 안되는지 검사하고, 2 + 3 + 4 + ... 해서 n이 되는지 안되는지 검사하는 방식이다.
중요한 것은 반복문을 돌리는 구간을 어느 정도로 잡느냐라고 할 수 있다.
일단 연속적인 자연수로 표현해야 하기 때문에 임의의 수 X를 n에서 뺐을 때 자신보다 작은 값이라면 그것은 후보에서 제외해야 한다. 왜냐하면 자신을 선두로 연속적인 자연수로 표현할 수 없기 때문이다.
이 범위를 계산해보니 n을 절반으로 나눈 값을 기준으로 잡을 수 있었다. 15를 예로 들었을 때, 15의 절반인 7까지는 검사를 해봐야 하지만 8부터는 검사를 할 필요가 없다는 뜻이다.
수를 고정하고 계속 반복문을 돌리는 구간도 n // 2보다 하나 더 큰 수까지만 돌리면 된다. n이 짝수라면 결국 (n // 2) + (n // 2) = n이다. 홀수라면 (n // 2) + (n // 2) + 1 = n이다.
다른 사람의 풀이
def solution(num):
return len([i for i in range(1,num+1,2) if num % i is 0])숫자의 표현(프로그래머스 - level2) - https://ssungkang.tistory.com
위 글에서 15를 예시로 설명해주는데, 그 글을 보고 이해가 갔다. 근데 짝수 개의 연속된 자연수로 표현되면 어떻게 되는걸까?
