[python] 백준 9461. 파도반 수열

문제

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

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

---

풀이

사실 java로 푼 적이 있던 문제였는데, 5개월 전에 풀기도 했고... 파이썬으로 푼 건 아니라서 다시 한번 풀어봤다. 문제를 보자마자 설마 DP?라고 했는데 진짜였다.

 

- 아이디어

쉬운 DP 문제들은 숫자들이 어떻게 바뀌는지 경우의 수를 나열하다보면 자연스럽게 식이 보인다. 이번 문제 역시도 그런 문제였기 때문에 금방 풀 수 있었다. 

문제에서 알려줬듯이, P(1)~P(10)의 숫자가 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 라고 한다면 이제 이 예시를 잘 들여다보자. 

P(n) = P(n-2) + P(n-3)인거다. 이제 이걸 list로 저장해서 값을 불러오기만 하면 이 문제는 해결이 된다.

 

애초에 DP자체가 여러번 돌지 않게 이전에 계산한 값들을 저장해두고 사용하는 것이기 때문에 이 특징만 잘 기억하고 응용하면 쉽게 문제를 풀 수 있는 것 같다.

 

- 코드 구성

나는 알고리즘 문제를 풀 때, 노트에 코드를 쓸 과정을 글로 하나씩 적어서 짜는 편이다. 이 과정을 이야기해보자면...

 

1. 테스트케이스 T를 입력 받고 for문을 돌려 결과값을 result 배열에 저장. 나중에 sys.stdout.write로 출력

2. P(0)~P(n)까지의 값을 저장할 배열을 선언하고, [0],[1],[2]에 1을 미리 저장해둔다.

3. 들어오는 N 값까지 for문을 돌려서 나머지 값들을 넣어준다.

4. 그러고 result.append로 P(n) 값을 저장해준다. 

import sys

t = int(sys.stdin.readline().strip())
result = []

for i in range(t):
    n = int(sys.stdin.readline().strip())
    data = [1]*n
    for j in range(n):
        if j > 2:
            data[j] = data[j-2] + data[j-3]
    result.append(data[n-1])

sys.stdout.write("\n".join(map(str, result)) + "\n")

 

미리 예상한 과정과 달라진 건, 애초에 배열을 선언할 때 모두 1을 기본으로 넣어두고 n만큼 도는 for문에서 index값이 3이상부터 돌아갈 수 있도록 해놨다. 

 

성공!