문제 설명
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.완전탐색 코드
- 코드 설명
이중 for문으로 1~n까지의 숫자를 순차적으로 sum에 누적합 해주다가 sum==n이 되면 카운트 해준다. 카운트 해준뒤 i for문으로 돌아가 i+1부터 n까지의 누적합을 반복하며 구해준다. - 효율성에서 걸리지 않으려면 반복문 중간에 적절히 break를 해줌으로써 불필요한 반복문 연산을 제거
def solution(n):
answer = 0
for i in range(1,n+1):
sum=0
for j in range(i,n+1):
sum+=j
if sum==n:
answer+=1
break
elif sum>n:
break
return answer
print(solution(15)) 재귀 코드
이 문제를 재귀로도 풀 수 있는 방법이 있다.
코드를 참고했는데 눈으로는 이해가 안가서 열심히 시뮬레이션 돌리며 이해했다.
- 코드설명
n이 15일때 처음 재귀를 호출하면 매개변수 값이 아래와 같다.
여기서 재귀를 반복적으로 호출하며 n에 i값을 누적합한다.
누적합 한 n 과 i+1값을 다시 재귀함수 매개변수로 호출한다.
이걸 반복하면
def recursion(n,i,limit):
if n==limit:
return True
if n>limit:
return False
n+=i
return recursion(n,i+1,limit)
def solution(n):
answer=0
for i in range(1,n+1):
if recursion(i,i+1,n):
answer+=1
return answer
print(solution(15))재귀함수 호출시 n,i,num값의 변화를 보면 i값은 2->3->4->5 이렇게 하나씩 증가하는 걸 볼 수 있다.
n==num 혹은 n>num 조건에 만족하면 if 조건에 걸리면서 각각 True,False값을 반환한다.
배운점
문제를 보고 DP로 풀어보려고 점화식을 끙끙대면서 찾았는데 결국 못찾았다. 재귀로도 풀 수 있을 것 같다고 생각은 했는데 코드로 구현하는데에 실패했다. 재귀에 대한 공부가 좀 더 필요 할 것 같다.
결국 풀이를 참고하는데,완전탐색으로 이중for문 사용해 비교적 직관적으로 코드를 구현한 걸 보고 많이 배웠다. 다양한 알고리즘을 문제에 적용해보고 최적의 방법을 선택하는 연습을 해야할 것 같다.
