문제
https://school.programmers.co.kr/learn/courses/30/lessons/12914
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.
제한사항
- n은 1 이상, 2000 이하인 정수입니다.
입출력 예
입출력 예 #1
위에서 설명한 내용과 같습니다.
입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.
나의 풀이1 (실패)
def dfs(cnt, n):
global answer
if cnt == n:
answer += 1
return
elif cnt > n:
return
dfs(cnt+1, n)
dfs(cnt+2, n)
def solution(n):
global answer
answer = 0
dfs(0, n)
return answer % 1234567- 처음에 DP를 생각해보기도 했지만 어떻게 이전의 값을 이용해 현재의 값을 구할 수 있는지 접근 방식이 떠오르지 않았다.
- 그래서 재귀 함수를 이용해서 풀어봤는데 예제 테스트의 작은 값들만 통과하고, 답변 제출 결과 재귀 호출의 깊이 제한을 초과하면서
RecursionError가 발생했다.
다른 사람의 풀이
n번째 칸에 도달하기 위해서는 2가지 방법이 있다.
n-1칸에서 +1칸을 점프하거나n-2칸에서 +2칸을 점프하는 경우
즉, 마지막 점프가 1칸인지 2칸인지에 따라 두 갈래로 나뉘는 것이다.
예를 들어, n = 4일 때
n = 3칸에서 1칸 뛰기n = 2까지 가서 2칸 뛰기
이것을 점화식으로 나타내면 dp[i] = dp[i-2] + dp[i-1]이 된다.
-> n번째 칸에 도달하는 경우의 수 = n-2번째 칸에 도달하는 경우의 수 + n-1번째 칸에 도달하는 경우의 수
def solution(n):
if n < 3:
return n
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-2] + dp[i-1]
return dp[n] % 1234567- 점화식을 이용한 동적계획법 알고리즘으로 풀었다.
n번째 칸까지 발생하는 경우의 수를 저장하기 위한 리스트를 생성한다.- 다음 값을 구하기 위해 한 칸, 두 칸일 경우 발생하는 경우의 수는 직접 입력한다.
- 점화식을 이용해
n번째 칸까지 점프할 때 발생하는 경우의 수를 리스트에 저장해 나간다. - 최종적으로
dp[n]즉,n번째 칸에 도달하는 경우의 수 나누기1234567을 출력한다.
회고
- 피보나치 수열을 구하는 방법과 비슷한 문제였다.
- 접근 방식이 떠오르지 않을 때는
1부터 시작해 답을 출력해 보면서 규칙성을 찾아보자. - DP를 이용한 풀이에도 패턴이 있기 때문에, 많이 풀면서 점점 익숙해지면 스스로의 힘으로도 풀 수 있게 될 것이다!