🔎 문제설명
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 이하의 자연수 입니다.
💡 풀이 아이디어
1) 반복문1 :i를 1부터 n까지 순회한다.
2) 반복문2 :j를i부터 n까지 순회하면서, 연속된 자연수들의 합(s)에i부터 1씩 큰 수를 차례로 더한다.
3) 만약 연속된 자연수들의 합(s)이n이 되면 방법의 개수(cnt)를 1 추가하고 반복문2를 빠져나온다.
4) 위의 과정을 반복한다.
## 내 풀이
def solution(n):
cnt = 0 # 방법의 수
for i in range(1, n+1) :
s = 0 # 연속된 자연수들의 합(매번 초기화)
for j in range(i, n+1):
s += j
if s == n : # 연속된 자연수들의 합이 n이 되면
cnt += 1 # 방법 1추가
break
return cnt
print(solution(15))4
정확성 테스트는 통과했는데, 효율성 테스트를 통과 못했다.
현재의 알고리즘은 시간 복잡도가 O(N^2)이다. 이는 입력값(n)으로 10,000이 들어올 경우 for loop의 반복 횟수가 100002 = 100,000,000(1억)에 비례함을 뜻한다. 이 정도 크기라면 C++과 같이 빠른 언어에서야 아슬아슬하게 시간 제한을 통과할 정도일 것이다. Python은 상대적으로 느리기 때문에 효율성 테스트를 통과하지 못하는 것이다.
위의 풀이를 아래와 같이 수정해보았다.
## 내 풀이 (수정)
def solution(n):
cnt = 0 # 방법의 수
for i in range(1, n+1) :
s = 0 # 연속된 자연수들의 합(매번 초기화)
for j in range(i, n+1):
s += j
if s == n : # 연속된 자연수들의 합이 n이 되면
cnt += 1 # 방법 1추가
break
# 추가한 코드
elif s > n: # 연속된 자연수들의 합이 n보다 크면
break # 고려할 필요 x => 반복문 탈출
return cnt
print(solution(15))'추가한 코드' 부분을 살펴보면 연속된 자연수들의 합(s)이 n보다 큰 경우에 대해서는 고려할 필요 없이 바로 반복문을 탈출하도록 되어있다. 이전 코드에서는 해당 코드가 없어서 s > n의 경우도 모두 탐색했기 때문에 n이 커질수록 시간초과로 에러가 떴을 것이다.
이 문제에서 집중해야 할 부분은 s == n 까지임을 명심하자.
다른 풀이를 찾아보니까 DP(동적계획법)를 활용해서 해결할 수도 있다고 한다.
## 다른 풀이
def solution(n):
answer = []
temp = []
for i in range(1,n+1):
if n % i == 0:
temp.append(i)
for i in range(len(temp)):
if temp[i] % 2 != 0:
answer.append(temp[i])
return len(answer)DP에 대한 개념은 아래 링크를 참고해서 복습한 후에 풀이를 살펴보도록 하자.
