백준 9461번 파도반 수열
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 114673 | 51497 | 42254 | 43.546% |
문제
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.
N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)
[출력]
각 테스트 케이스마다 P(N)을 출력한다.
문제 해석하기
-
일단 해당하는 파도반 수열의 규칙에 대해 알아야겠다는 생각을 했다.
- 파도반 수열의 특징:
- P(1)=1, P(2)=1, P(3)=1
- P(4)=2, P(5)=2
- P(n) = P(n-1) + P(n-5)
-
점화식 적용:P(n)=P(n−1)+P(n−5)를 기반으로 n번째 수를 계산한다.
-
메모이제이션: 이미 계산한 값을 배열에 저장하여 중복 계산을 방지한다.
-
입력 처리 및 출력: 주어진 t개의 테스트 케이스에 대해 각각 P(n)을 출력한다.
-
sys.stdin.read를 이용해서 입력을 한번에 읽어들인다.
-
dp배열을 초기화해서 각각의 P(1)부터 P(5)까지의 값을 설정한다.
-
dp의 값을 계산해주고, 점화식을 활용한다.
def solve_wave_sequence():
import sys
input = sys.stdin.read
data = input().split()
t = int(data[0])
cases = list(map(int, data[1:]))
max_n = max(cases)
dp = [0] * (max_n + 1)
dp[1], dp[2], dp[3] = 1, 1, 1
if max_n >= 4:
dp[4], dp[5] = 2, 2
for i in range(6, max_n + 1):
dp[i] = dp[i - 1] + dp[i - 5]
results = [dp[n] for n in cases]
print("\n".join(map(str, results)))
solve_wave_sequence()오늘의 회고
오늘도 동적 프로그래밍에 관련한 문제를 풀어봤는데, 아직까진 그래도 어렵게 느껴지는 것 같다. 그래도 문제를 풀어보면서 해결해나갈 수 있어서 의미있다고 생각한다
