[알고리즘] 백준 9461 파도반 수열 (파이썬 풀이)

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

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)을 출력한다.

 

해결코드

import sys

input = sys.stdin.readline

t = int(input())

li = [0]*101
li[1]=1
li[2]=1
li[3]=1
for i in range(4,101):
    li[i] = li[i-2] + li[i-3]

for i in range(t):
    n = int(input())
    print(li[n])

문제풀이

dp를 이용하는 문제이다.

문제에서 규칙을 찾아 점화식을 세우면 된다.

 

수의 진행이 1, 1, 1, 2, 2, 3, 4, 5, 7, 9.... 이렇게 가고 있는데 자세히 보면

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

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

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

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

이런 식으로 연속된 앞의 값 두 개를 더하면 두칸 뒤의 값이 나오는 것을 알 수 있다.

점화식을 세우면 li[i] = li[i-2] + li[i-3] 이런 느낌이다.

 

코드를 보자

 

입력시간을 줄이기 위해 sys라이브러리를 사용한다.

 

t = int(input())

t에 테스트케이스 수를 입력받는다.

li = [0]*101
li[1]=1
li[2]=1
li[3]=1

li라는 리스트를 생성하고 101개의 원소를 0으로 선언한다(101개인 이유는 1부터 시작하기 때문이다)

그리고 기본 값으로 li[1],li[2],li[3] 값을 지정해준다.

for i in range(4,101):
    li[i] = li[i-2] + li[i-3]

나머지 값들(4~100)는 for문을 실행시킨다.

아까 세운 점화식을 가지고 나머지 원소 값들을 구할 수 있다.

for i in range(t):
    n = int(input())
    print(li[n])

이번엔 테스트케이스 수만큼 for문을 돌린다.

n을 입력받고

아까 구했던 li[n]을 출력해준다.