문제링크 : https://www.acmicpc.net/problem/9461
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
작성코드
풀이
1) 규칙 찾기
도형의 접하지 않는 건너편 2개의 큰 삼각형 변 길이 합이 이번 삼각형의 변 길이가 됨을 찾을 수 있다.
P = [1, 1, 1, 2, 2, 3, 4, 5, 7 ,9, 12]
수열로서 찾아도 확인이 가능하다.
수식으로 보자면 P[N] = P[N-2] + P[N-3]의 값이 나오는 것을 찾을 수 있다.
2) 구현하기
찾은 규칙에 따라 리스트에 저장해 주는데
테스트 마다 매번 계산할 필요가 없도록 리스트에 저장을 해둔다.
만약 기본값 0이 있다면 처음 계산하므로 넘어가고
이미 값이 있다면 기존에 계산해둔 값을 사용한다.
그렇게 계산한 값을 출력해주면 정답이 나온다.
P[N-1]을 출력하는 이유는 인덱스는 0부터 시작이지만 구하고자 하는 값 입력은 1부터 입력 받기 때문에 N-1을 출력해준다.
'백준 > Python' 카테고리의 다른 글
| [백준] 1932 정수 삼각형 (python 파이썬) (0) | 2022.11.27 |
|---|---|
| [백준] 1912 연속합 (python 파이썬) (0) | 2022.11.27 |
| [백준] 11659 구간 합 구하기 (python 파이썬) (0) | 2022.11.24 |
| [백준] 1149 RGB거리 (python 파이썬) (0) | 2022.11.16 |
| [백준] 1904 01타일 (python 파이썬) (0) | 2022.11.14 |