[백준] 9461번 - 파도반 수열 (DP) - 결과 포함

www.acmicpc.net/problem/9461

9461번: 파도반 수열

문제를 읽고 그림 예시를 보니 규칙성이 눈에 띄었다.

처음에는 어떻게 풀어야 할 지 해결 방법이 떠오르지 않았지만,

무언가 규칙이 존재할 것 이라는 생각을 지울 수 없었다.

이 문제가 다이나믹 프로그래밍 분류에 있는 문제라고 생각해서 떠올랐을 가능성이 크다고 생각한다.

 

1, 1, 1, 2, 2, 3, 4, 5, 7 ,9

 

위 수열은 문제에 나와있는 파도반 수열 P(10)의 숫자들이다.

 

규칙을 찾기 위해서 계속 삼각형 그림을 보다가

큰 삼각형들은 작은 삼각형들이 모여서 이루어진다는 생각을 했고

 

앞에 있는 숫자들의 조합으로 뒤에 있는 숫자들이 나올 수 있다고 생각했다.

4 번째 숫자인 2가 나오기 위해서는 어떻게 해야할까를 생각했다.

앞에 1과 1을 더하면 2가 나온다.

 

그런데 그 뒤에도 2가 나온다.

여기서 힌트를 얻었다. 왜냐하면 앞에 1이 3개가 있었기 때문이다.

첫 번째 1과 두 번째 1을 더해서 앞에 있는 2가 나오고

두 번째 1과 세 번째 1이 더해져서 뒤에 있는 2가 나올 수 있겠다는 의심을 하기 시작했다.

 

결과적으로 이 수열에서 특정한 숫자는 앞앞앞 숫자와 앞앞 숫자를 더한 결과라는 것을 깨달았다.

 

[소스 코드]

def P(n):
    if n == 1 or n == 2 or n == 3:
        return 1
    for i in range(4, n + 1):
        d[i] = d[i - 3] + d[i - 2]
    return d[n]


t = int(input())
d = [0] * 101
d[1] = 1
d[2] = 1
d[3] = 1
for _ in range(t):
    n = int(input())

    print(P(n))