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)을 구하
www.acmicpc.net
내 코드
| 0 번 | 1 번 | 2 번 | 3 번 | 4 번 | 5 번 | 6 번 | 7 번 | 8 번 | 9 번 |
| 1 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 7 | 9 |
9번 수 : 9 = 4 + 5 = 6번 수 + 7번 수
8번 수 : 7 = 3 + 4 = 5번 수 + 6번 수
7번 수 : 5 = 2 + 3 = 4번 수 + 5번 수
6번 수 : 4 = 2 + 2 = 3번 수 + 4번 수
5번 수 : 3 = 1 + 2 = 2번 수 + 3번 수
4번 수 : 2 = 1 + 1 = 1번 수 + 2번 수
3번 수 : 2 = 1 + 1 = 0번 수 + 1번 수
2번 수 : 1 = 1
1번 수 : 1 = 1
0번 수 : 1 = 1
위와 같이 정리하면 다음과 같은 식을 유추할 수 있다.(0에서 2번까지의 제외)
padovan[N] = padovan[N-3] + padovan[N-2]
이것을 배열로 만들어서 맨 마지막 수를 출력하면 된다.
|
def padovan(N):
# 1로 초기화 하여 0번부터 2번까지 수 입력
padovan_list = [1] * N
for i in range(3, N):
padovan_list[i] = padovan_list[i-3] + padovan_list[i-2]
return padovan_list[-1]
if __name__=='__main__':
# T 입력 받기
for i in range(int(input())):
# N 입력 받기
answer = padovan(int(input()))
print(answer)
|
'알고리즘 > 백준' 카테고리의 다른 글
| [python/1932]정수 삼각형 (0) | 2020.04.16 |
|---|---|
| [python/1149]RGB거리 (0) | 2020.04.14 |
| [python/1904]01타일 (0) | 2020.04.09 |
| [python/1003]피보나치 함수 (0) | 2020.04.07 |
| [python/2748]피보나치 수2 (0) | 2020.04.02 |