[BOJ/백준] 9461번 - 파도

단계별로 풀어보기 > 동적 계획법 1 > [4단계] 9461번

 

문제 링크 : https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

 

 

문제 요약

1. 주어진 문제에 대한 규칙을 찾아 점화식을 세운다.

 

입력 복사

예제 입력 1 >> 출력 : 3 16

2
6
12

 

CODE

#include <bits/stdc++.h>
using namespace std;

long long term[1000];
long long dp(int n) {
	
	if(n == 0 or n == 1 or n == 2) return 1;
	
	if(term[n] != 0) return term[n];
	
	else {
		term[n] = dp(n-2) + dp(n-3);
		return term[n];
	}
}

int main() {
	int t;
	int n;
	cin >> t;
	
	
	for(int i=0; i<t; i++) {
		cin >> n;
		cout << dp(n-1) << endl;
	}

}

 

문제 풀이

1. 규칙을 찾아 '점화식 : n = (n-2) + (n-3)'을 구한다.

2. Memoization 방식을 적용한다. (안하면, 시간초과가 나오더라구요.)

 

시간 초과 코드(재귀 코드)

#include <bits/stdc++.h>
using namespace std;

long long dp(int n) {
	
	if(n == 0 or n == 1 or n == 2) return 1;
	
	else {
		return dp(n-2) + dp(n-3);
	}
}


int main() {
	int t;
	int n;
	cin >> t;
	
	
	for(int i=0; i<t; i++) {
		cin >> n;
		cout << dp(n-1) << endl;
	}

}

 

주의할 점

1. 피노나치 수열와 유사한 경우 자료형에 주의한다.

- Testcase도 맞고, 출력도 일치하는 데 답이 틀리는 경우의 대부분에 해당한다.

- 예를 들어, 90번째 피보나치 수는 int형 범위를 초과한다. 그러므로 long long을 사용한다.

 

2. 시간 초과

- 동적 프로그래밍의 특징은 재귀 함수의 효율적인 계산을 위해 메모이제이션을 사용하는 점이다.

- 단순 재귀로는 시간 초과의 우려가 있으니 메모이제이션을 활용하자!

 

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. (출처 : 위키백과)

 

 

참고하면 좋은 Memoization 글

https://www.geeksforgeeks.org/memoization-1d-2d-and-3d/

Memoization (1D, 2D and 3D) - GeeksforGeeks