[백준] 9461번 : 파도반 수열

 

 

 

접근법 

- 나선 모양 중에서 반복이 되는 1과 2를 뛰어넘고 3부터 규칙을 찾아보았다. 

 

- 3을 기준으로 맨 처음의 값(P[1], 편의 상 P[0]는 건너뛰고 1부터 시작했다.)과 맨 마지막 값(P[3 - 1])을 더하니 3이 나오는 것을 알 수 있었다.

 

- 그 다음 값인 4는 P[2]와 P[4 - 1], 5는 P[3]와 P[5 - 1] 이런 규칙이 있다는 것을 알 수 있었다.

 

- start_idx를 1로 설정하고 3의 인덱스인 6부터 N의 최댓값인 100까지의 for문을 돌면서 P[i]의 값을 구하고 start_idx를 1씩 올려주며 값을 계산했다.

 

- 다 풀고 다른 분들은 어떻게 풀었나 봤더니 P[i + 3] = P[i] + P[i + 1] 규칙을 이용해서 풀었다. 

 

 

 

 

 

풀이

# 백준 9461번 : 파도반 수열

num = int(input())
P = [0 for _ in range(101)]

P[1] = 1
P[2] = 1
P[3] = 1
P[4] = 2
P[5] = 2

start_idx = 1

for i in range(6, len(P)) :
    P[i] = P[i - 1] + P[start_idx]
    start_idx += 1

for _ in range(num) :
    N = int(input())
    print(P[N])

 

 

 

 

 

결과