[백준] 9461번 파도반 수열 C 해설 (다이나믹 프로그래밍)

출처 : https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

다이나믹 프로그래밍(DP) 알고리즘으로 분류되어있는 문제이다.

이제 DP알고리즘은 정말 잘 푸는 것 같다. 물론 아직 갈 길은 멀다!

이번에는 파이썬이 아니라 C로 풀어봤다.

 

풀이

---

다이나믹 프로그래밍 알고리즘 문제는 사실 보기에서 주어지는 그림이 크게 중요한 역할을 하는 것 같진 않다. 문제에서 주어지는 조건을 만족하는 점화식을 찾는 게 포인트라고 생각한다.

한 가지 주의 할 점은 n의 범위이다.
n은 1이상 100 이하라고 정의했는데, 문제를 풀어보면 알겠지만 int의 범위를 초과하게 된다.

이러한 점을 유의하여 제출한 정답 코드이다.

#include <stdio.h>

int main() {
	int n, i, buf;
	long long dp[101] = { 0, 1, 1, 1 };
	
	for (i = 4; i < 101; i++)
		dp[i] = dp[i - 2] + dp[i - 3];
	
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &buf);
		printf("%lld\n", dp[buf]);
	}
	
	return 0;
}

dp배열의 크기를 101로 선언 한 이유는 입력이 인덱스 기준이 아니기 때문이다. (n = 100일 때 그냥 쉽게 dp[100]으로 접근하기 위함이다.)

 

결과

---

오늘도 기분 좋게 한 번의 시도만에 정답을 맞혔다.

당분간은 C언어를 주로 사용하여 문제를 풀 것 같다.
(SK 주식회사 C&C 서류합격으로 코딩 시험을 보게 됐는데 C언어를 사용하기 때문이다.)