✅Lv3. 멀리 뛰기

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12914#

코딩테스트 연습 - 멀리 뛰기

 

#1. 개선할 점

 

- 처음에는 DFS 재귀로 풀려고했는데 n이 최대 2000이므로 연산을 최대 O(2^2000)번 해야해서 시간초과가 난다.

 

BFS도 visited를 관리해서 이미 방문한 노드를 다시 방문하지 않으면 O(V+E)이지만,

이 문제에서는 방문한 노드들을 관리하지 않으므로 BFS도 DFS와 같이 시간초과가 난다.

 

따라서 수학적인 규칙을 찾아보려고 했다.

 

맨 처음엔 2칸의 개수와 그에따른 1칸의 개수를 구한 뒤,

개수가 큰 값을 기준으로 큰값+1C작은값을 해서 구하려고 했지만 계속 틀려서 보니까

몇가지 경우가 빠진다는 걸 확인할 수 있었다.

 

ex) 1칸의 개수 : 2, 2칸의 개수 : 2

_ 1 _ 1 _ -> 3C2

-> 1122인 경우가 고려되지 않는다!!!!!!!!!!!!! (이게 안된다는 걸 알 때까지 너무 오래걸렸다 .......)

 

2칸의 개수를 0부터 가능할 때 까지 반복하면서 중복순열의 개수를 구하는 방법으로 바꿨더니 맞았다.

 

from math import factorial

def solution(n):
    answer = 0
    for i in range(n//2+1) :
        num1 = n - 2*i		#1칸의 개수
        num2 = i		#2칸의 개수(i지만 직관적으로 보기위해 이렇게 작성함)
        
        answer += factorial(num1+num2) // factorial(num1) // factorial(num2)
    
    return answer % 1234567

 

+) 완탐 실패했을 때는 DP를 생각해보자 !!!!!!!

 

문제를 쪼개보고, 쪼갠 것들간의 관계를 살펴보자.

서로 영향을 주거나 중복되는게 있다면 dp 점화식을 세울 수 있다.

 

계단을 1칸, 2칸씩만 올라갈 수 있으므로 매 칸마다 가능한 방법의 수를 dp로 구해보자.

1칸 = [1] -> 1가지

2칸 = [1, 1], [2] -> 2가지

 

3칸 = 1칸에서 2칸 올라와서 오는 경우 + 2칸에서 1칸 올라와서 오는 경우

[1, 2]

[1, 1, 1], [2, 1]

-> 3가지

 

4칸 = 2칸에서 2칸 올라와서 오는 경우 + 3칸에서 1칸 올라와서 오는 경우

[1, 1, 2], [2, 2]

[1, 2, 1], [2, 1, 1], [1, 1, 1, 1]

-> 5가지

...

 

따라서 dp[i] = dp[i-1] + dp[i-2]같은 점화식을 세울 수 있다.

 

def solution(n):
    if n == 1 : # 주의!! 초기값으로 지정되는 경우는 바로 리턴해주는 것이 런타임에러 방지에 좋다.
        return 1
    elif n == 2 :
        return 2
    
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n+1) :
        dp[i] = dp[i-1] + dp[i-2]
        
    return dp[n] % 1234567