서론
본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다.
대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다.
문제
Baekjoon 9461번 - 파도반 수열:
https://www.acmicpc.net/problem/9461
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
해법
이번 문제는 파도반 수열의 N 번째 숫자를 구하는 문제였다. 파도반 수열은 다음과 같은 규칙을 가지고 있다.
(*P는 파도반 수열을 말함)
Pn = Pn-2 + Pn-3 (P1 = 1, P2 = 1, P3 = 1)
위 규칙을 보면 피보나치 수열과 유사하다는 것을 알 수 있다. 우리는 이번 문제에도 Bottom-Up Dynamic Programing을 적용할 수 있을 것이다. 그런데 이번엔 문제의 입력 테스트케이스가 여러개가 주어지는데, 입력 N의 값이 달라져도 계산된 파도반 수열의 값은 재활용이 가능하기 때문에 Memoization을 통해 계산된 값들을 저장해두면 공간복잡도 O(1)으로 이번 문제를 해결 할 수 있을 것이다.
풀이
참고자료
위키피디아 - 동적계획법:
https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95
동적 계획법 - 위키백과, 우리 모두의 백과사전
수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분
ko.wikipedia.org
'SW > Baekjoon' 카테고리의 다른 글
| [Baekjoon 문제풀이] 11653 - 소인수분해 (Python 3) (0) | 2022.01.04 |
|---|---|
| [Baekjoon 문제풀이] 4153 - 직각삼각형 (Python 3) (0) | 2022.01.04 |
| [Baekjoon 문제풀이] 2748 - 피보나치 수 2 (Python 3) (0) | 2022.01.04 |
| [Baekjoon 문제풀이] 2581 - 소수 (Python 3) (0) | 2022.01.04 |
| [Baekjoon 문제풀이] 2609 - 최대공약수와 최소공배수 (Python 3) (0) | 2022.01.04 |