백준 알고리즘 9461 (파도반 수열) - C++, Python

[문제] 백준 알고리즘 9461 (파도반 수열)

> https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

나선에서 가장 긴 변의 길이를 갖는 정삼각형을 계속 추가하는 수열 문제이다.

DP문제이며, 점화식을 구해야하므로 아래처럼 표를 작성하여 규칙을 찾는다.

N	0	1	2	3	4	5	6	7	8	9
길이	X	1	1	1	2	2	3	4	5	7
N=4		+		+	1+1=2
N=5		+			+		1+2=3
N=6			+				+	1+3=4
N=7				+				+	1+4=5
N=8					+				+	2+5=7
점화식 : dp[n] = dp[n-1] + dp[n-5] (n >= 7)

점화식 dp[n] = dp[n-1] + dp[n-5] (n >= 7)을 알 수 있다.

 

[문제 해결]

1. 테스트 갯수 t를 받고, dp[101]을 선언

2. dp[6]까지 초기값으로 할당

3. dp[7]부터 101번째까지 dp[n] = dp[n-1] + dp[n-5]대로 값 할당

4. n 입력에 따라 dp[n] 출력

 

[C++]

#include <cstdio>
#include <cstring>
using namespace std;

long long dp[101] = { 0, 1, 1, 1, 2, 2, 3 };

void wave() {
	for (int i = 7; i <= 101; i++) {
		dp[i] = dp[i - 1] + dp[i - 5];
	}
}

int main() {
	int T;
	scanf("%d", &T);
	wave();
	for (int t = 0; t < T; t++) {
		int n;
		scanf("%d", &n);
		printf("%lld\n", dp[n]);
	}
	return 0;
}

 

[Python]

import sys
input = sys.stdin.readline
t = int(input())
dp = [0 for _ in range(101)]

def wave():
    dp[1], dp[2], dp[3] = 1, 1, 1
    dp[4], dp[5] = 2, 2
    dp[6] = 3
    for i in range(7, 101):
        dp[i] = dp[i-1] + dp[i-5]
    return

for _ in range(t):
    n = int(input())
    wave()
    print(dp[n])