다이나믹 프로그래밍 정복기4 - 규칙을 찾으면 되는 쉬운문제들1-

1. 문제1

 

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

9461번: 파도반 수열

 

나선형으로 정삼각형을 만들었을때, 정삼각형의 가장 긴 변의 길이를 구하는 방법은?

 

 

2. 풀이1

 

이런 문제는 그냥 몇개 나열해보면서 규칙을 찾으면 되겠다고 생각하는게 제일 편하다

 

이런 규칙 찾는 문제가 다이나믹 프로그래밍의 가장 기본형태라고 생각하면 된다

 

그래서 몇개 해보면 규칙이 나올거야

 

p(1)부터 p(10)까지는 1,1,1,2,2,3,4,5,7,9라고도 친절하게 나와있고

 

그림에서 p(11)은 12이고..

 

 

그림 그리다보면.. N번째 삼각형의 변의 길이는 바로 이전 삼각형의 변에 5번째 전의 삼각형의 변의 길이의 합

 

P(N) = P(N-1) + P(N-5)와 같다는 것을 알 수 있다

 

 

from sys import stdin

p = [0] * 101

p[1] = 1
p[2] = 1
p[3] = 1
p[4] = 2
p[5] = 2

for i in range(6,101):
    
    p[i] = p[i-1]+p[i-5]

T = int(stdin.readline())

for _ in range(1,T+1):
    
    n = int(stdin.readline())

    print(p[n])

 

2. 문제2

 

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

9095번: 1, 2, 3 더하기

 

정수 n을 1,2,3의 합으로 나타내고자 할 때 방법의 수를 구하는 프로그램을 작성

 

 

3. 풀이2

 

단순히 경우의 수를 나열해서 규칙을 보면..?

 

기본적으로 1,2,3인 경우는 각각 1,2,4가지가 있고

 

 

n=4부터 4는 7이라고 문제에 나와있고

 

 

 

문제 예시 케이스까지 생각하면

 

1,2,4,7,13, ? , 44,...

 

근데 7은 4+2+1

 

13 = 7+4+2 이여서 ? = 13+7+4 = 24

 

44 = 24 + 13 + 7이니까 이전 3개의 수의 합으로 구해질 수 있다는게 눈치?로 알 수는 있는데

 

왜 그런지 한번 좀 생각해보면

 

--------------------------------------------------------

n=4인 경우는

 

3에다가 1을 더한것이므로, 3의 경우의 수에 그냥 1만 더하면 되니까 4가지를 그대로 가져가고

 

2에다가 2를 더한 것이므로 2의 경우의 수에 그냥 2만 더하면 되니까 2가지를 그대로 가져가고

 

1에다가 3을 더한 것이므로 1의 경우의 수에 그냥 3만 더하면 되니까 1가지를 그대로 가져가서

 

n=4는 4+2+1 = 7이 된다

-------------------------------------------------------

 

n=5인 경우도 마찬가지다

 

4에다가 1을 더한 것이므로, 4의 경우의 수에 그냥 1만 더하면 되니까 7가지를 그대로 가져가고

 

3에다가 2를 더한 것이므로, 3의 경우의 수에 그냥 2만 더하면 되니까 4가지를 그대로 가져가고

 

2에다가 3을 더한 것이므로 2의 경우의 수에 그냥 3만 더하면 되니까 2가지를 그대로 가져가서

 

n=5는 7+4+2=13이 된다

 

----------------------------------------------------

 

 

 

from sys import stdin

dp = [0] * 11

dp[1] = 1

dp[2] = 2

dp[3] = 4

for i in range(4,11):
    
    dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

T = int(stdin.readline())

for _ in range(T):
    
    n = int(stdin.readline())
    
    print(dp[n])