[Python] 16456번 하와와 대학생쨩 하와이로 가는 거시와요~ (추후 보강 예정)

16456번: 하와와 대학생쨩 하와이로 가는 거시와요~ (acmicpc.net)

16456번: 하와와 대학생쨩 하와이로 가는 거시와요~

---

 

22/09/03

 

 

그룹 연습에서 푼 문제로, DP문제여서 몇 개 나열해보다가 신뢰의 제출을 해서 맞았다.

---

 

문제 접근 방식:

 

먼저 숫자를 몇 개 구해봤다. 그래서 점화식을 dp[i] = (dp[i-1] + dp[i-3]) 과 같이 유추를 했는데, 그에 대한 정당성을 세워야만 했다.

 

근데 아직까지 정당성을 세우지는 못했다. 이후 정당성을 세운다면, 보충해서 작성할 예정이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 16456번 하와와 대학생쨩 하와이로 가는 거시와요~
# DP
dp = [0 for _ in range(50001)]
dp[1], dp[2], dp[3] = 1, 1, 2
N = int(input())
if N <= 3:
    print(dp[N])
else:
    for i in range(4, N+1):
        dp[i] = (dp[i-1] + dp[i-3]) % 1000000009
    print(dp[N])