9461:파도반 함수(DP)

 

https://www.acmicpc.net/problem/9461

 

 

나선으로 돌아가면서 커지는 도형의 가장 긴 변의 길이는 구하는 문제인데, 이건 딱 봐도 Dp구나 싶어서 n번째의 길이와 그 앞의 길이와의 관계들을 살펴보았다.

 

내가 직관적으로 그림을 통해 확인했던 건 dp[i] = dp[i-1]+dp[i-5]였기 때문에 기본 값들을 세팅해주고 식을 넣어 문제 풀이를 하였다.

 

 

 

 

 

 

* 나의 코드

t = int(input())
dp =[0]*101
dp[1]=1
dp[2]=1
dp[3]=1
dp[4]=2
dp[5]=2
dp[6]=3
dp[7]=4
dp[8]=5


for _ in range(t):
    n = int(input())
    if n>8:
        for i in range(8,n+1):
            dp[i] = dp[i-1]+dp[i-5]
    print(dp[n])

 

 

 

 

 

# 다이나믹 프로그래밍 문제 시 해야 할 것

1. 값들의 관계 파악하기(실질적으로 제일 중요한 것임)

2. dp list 생성한 후(몇번째까지 생성해야하는지 문제에서 제공된다) 기본 값 넣어주기

3. for 문으로 값들의 관계를 이용한 dp 값들 생성하여 정답찾기(메모이제이션)

 

추가로, 다이내믹 프로그래밍 문제를 해결하는 방법에는 2가지가 있는데, 내가 이 문제를 해결한 것처럼, 아래 값들부터 for문을 통해 순차적으로 가장 뒤의 dp index까지 가는 방법을 bottom up 방식이라고 하고, 위의 값부터 달라고 바로 제시해 재귀함수를 통해 알고 있는 기본 세팅 index 값까지 간 다음 해결하는 방법을 top down 방식이라고 한다.

 

다이내믹 프로그래밍을 처음 알고 공부했을 때는 메모이제이션, bottom up 과 top down 모두 어려운 말처럼 들렸는데 직접 문제를 통해 적용하다 보니 굉장히 직관적으로 지어진 말들이라고 생각된다. 다이내믹 프로그래밍 빼고....

 

 

 

요즘 다이내믹 프로그래밍 관련된 예제들을 풀이하면서 이 3가지만 따라주면 기초적인 관련 문제들은 모두 풀 수 있겠다는 생각이 들었다. 다시 한 번 강조할 내용은 값들의 관계 파악을 잘하는 것이 핵심이다! 라는 것이다.