https://www.acmicpc.net/problem/9461
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
문제는 다음과 같다.
P(1)부터 P(10)까지의 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 로 정삼각형의 변의 길이를 나타낸다. 이는 수열 형태이므로, Dynamic Programming을 활용하여 문제를 풀고자하면 된다.
DP이긴 하지만, 본래의 DP처럼 생각하고 점화식을 굳이 안세워도 이미 주어진 파도반 수열이 있기에 어렵지 않게 풀 수 있었다.
Padovan sequence(파도반 수열)
initialization value P(0), P(1), P(2) is 1, after value represent P(n) = P(n - 2) + P(n - 3) where n > 2.
초기값 P(0)부터 P(2)까지는 1이며, 이후부터는 P(n - 2) + P(n - 3) = P(n) 점화식을 활용하여 DP table을 채워나가면 된다.
N의 범위가 0부터 100까지이므로, 미리 100까지 DP table을 만들었다.
이후, 들어오는 입력값을 바로 DP table 요소에 접근하여 출력하게끔 하였다.
아래는 위의 설명대로 작성된 코드이다.
게시글을 안올렸을 뿐, 1일 1백준은 안끊겼다리
1일 1백준 33일째..
골드2 승급까지 절반남았다..!
'백준에 대가리 깨지는중' 카테고리의 다른 글
| [백준] 실버1 트리순회 (1) | 2023.06.28 |
|---|---|
| [백준] 골드4 DSLR (3) | 2023.06.22 |
| [백준] 실버1 가장 가까운 세 사람의 심리적 거리 (2) | 2023.06.07 |
| [백준] 실버1 경로 찾기 (0) | 2023.06.06 |
| [백준] 실버1 쉬운 최단거리 (0) | 2023.06.05 |