[solved.ac 실버3] 9461_파도반 수열 (DP 풀이)

제한 사항

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 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)을 출력한다.

예제

 

---

나의 풀이

(좌) 한 변의 길이, (우) 인덱스

왼쪽의 그림은 문제에서 주어진 그림이다. 숫자는 삼각형 한 변의 길이를 뜻한다.

오른쪽 그림은 내가 새로 번호를 부여한 그림이다. 숫자는 인덱스를 뜻한다.

삼각형의 한 변 길이는 다른 삼각형 하나 혹은 2개의 한 변 길이의 합이다.

예를 들어 오른쪽 그림에서 10번 인덱스 삼각형의 한 변 길이는 5번 인덱스와 9번 인덱스의 변 길이희 합이다.

그래서 삼각형의 한 변이 어떤 삼각형들로 이루어지는지 찾아보았다.

• 0번 삼각형 -> 혼자 세워짐
• 1번 삼각형 -> 0번 삼각형
• 2번 삼각형 -> 1번 삼각형
• 3번 삼각형 -> 0번 삼각형, 2번 삼각형
• 4번 삼각형 -> 3번 삼각형
• 5번 삼각형 -> 0번 삼각형, 4번 삼각형
• 6번 삼각형 -> 1번 삼각형, 5번 삼각형
• 7번 삼각형 -> 2번 삼각형, 6번 삼각형
• 8번 삼각형 -> 3번 삼각형, 7번 삼각형
• 9번 삼각형 -> 4번 삼각형, 8번 삼각형
• 10번 삼각형 -> 5번 삼각형, 9번 삼각형
• ...

패턴이 보이는가?

5번 삼각형부터는 일정한 패턴을 보이고 있다.

i번째 삼각형 변의 길이는 i-5번째 삼각형과 i-1번째 삼각형의 변의 길이의 합으로 이루어진다. (단, i >= 5)

패턴을 찾았으니 DP 테이블을 그릴 수 있다.

DP 테이블에는 삼각형의 한 변 길이가 저장된다.

0번~4번 삼각형은 직접 구해서 저장한다.

d = [1, 1, 1, 2, 2]

5번 삼각형 이후부터는 위에서 찾은 패턴에 따라 구한다. (문제에서 N이 최대 100까지 주어진다고 했으니 크기가 100이 넘는 DP 테이블을 만들면 된다.)

for i in range(5, 101):
    d.append(d[i-5]+d[i-1])

위 과정이 끝나면 d에는 1~100 까지 모든 삼각형의 한 변의 길이가 저장되어 있다.

단순히 숫자를 입력 받아 1을 뺀 만큼의 위치의 값을 출력하기만 하면 된다.

t = int(input())
for _ in range(t):
    print(d[int(input())-1])

 

전체 코드

d = [1, 1, 1, 2, 2]
for i in range(5, 101):
    d.append(d[i-5]+d[i-1])

t = int(input())
for _ in range(t):
    print(d[int(input())-1])

 

채점 결과