백준_22236_가희와 비행기(python)

★ 접근

적당히 큰 입력 값의 크기, 구해야 하는 모든 경우의 수들을 종합적으로 봤을 때 바로 다이나믹 프로그래밍을 떠올렸다.

 

★ 풀이

1. 비행을 할 때 한 지점에 도달할 수 있는 경우의 수는 이전 x좌표에서 아래에서 위로 올라온 것과 이전 x좌표에서 위에서 아래로 내려온 경우의 수를 합친 경우이다. 

2. 1번이 전부이다.... 항상 dp가 그렇죠 뭐..... 점화식만 세우면 끝이니... 근데 이 정도로 간단할 줄은.... 그래도 골드4인데... 황당...

 

- 코드

import sys
input = sys.stdin.readline
d,m = map(int,input().split())
dp = [[0] * 4001 for _ in range(4001)]
dp[1][1] = 1
for i in range(2,d): # d-1 까지만 가는 이유 마지막 d일때는 그냥 직전 위치 높이 1에서 내려오는 방법밖에 없으니
    for j in range(1,i+1): # 해당 좌표까지는 해당 높이까지만 올라갈 수 있으므로 i+1까지 가준다. 1부터시작해야지
        dp[i][j] += (dp[i-1][j-1] + dp[i-1][j+1]) % m

print(dp[d-1][1])

★ 회고

흠..... 항상 dp만 보면 일일이 손 코딩을 해서 점화식을 세우려고 한다 근데 이것은 문제의 난이도가 낮았을 때는 들어맞았는데 문제의 난이도가 올라갈 수록 손 코딩도 하기 어려워진다. 결국 생각하고 점화식을 세워야 한다.

 dp는 풀어도 풀어도 느낌이 잘 안 온다... 열심히 하자!!