알고리즘/백준[baekjoon]

[baekjoon] 백준 9461번 : 파도반 수열 (by python)

코딩하는이씨 2022. 7. 5. 21:16
728x90
반응형

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

 

9461번: 파도반 수열

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

www.acmicpc.net

 

정답 code

#파도반 수열
import sys
input = sys.stdin.readline

pado = [0 for _ in range(101)]
for i in range(1,101):
    if i == 1:
        pado[i] = 1
    elif i == 2:
        pado[i] = 1
    elif i == 3:
        pado[i] = 1
    elif i == 4:
        pado[i] = 2
    elif i == 5:
        pado[i] = 2
    else:
        pado[i] = pado[i-1] + pado[i-5]

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

 

solution

규칙만 찾으면 간단히 해결할 수 있다.

규칙이 몇가지 있는데 내가 사용한 규칙은 6번째부터 적용되는 규칙이다. 

P[n] = p[n-1] + [n-5] 규칙이다.

 

이것말고도 찾아본결과 

p[n+3] = p[n] +p[n+1] 규칙도 있다.

728x90
반응형