문제

백준 ( BOJ ) 2193번 이친수 (이천수 아닙니다..)

해결 방법 : 다이나믹 프로그래밍 ( DP )

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

문제 풀이

항상 다이나믹 프로그래밍 문제는

이전에서 추가되었을 때 어떤 규칙을 갖는가?

가 가장 중요합니다.

가장 쉬운 방법인 예시를 통해서 알아볼께요

N-2 : ..1—– N-1 : .1—— N : 1——-

여기서 이 문제에서 요구하는 해결방법 어떤게 있을까요?

우선 맨아래거를 봐봅시다.

10X—– 가 될 텐대요,

여기서 X가 1이냐 0이냐에 따라 바뀌는 것을 찾아 주면 됩니다.

그럼 우선 1인 것 부터 볼까요?

N-2는 10X 에서 X가 1인 모든 경우의 수를 포함 하고 있습니다.

그러면 간단하게 N-2 + X가 0인경우를 더하면 되는데

N-1 을 보시면 X 바로 앞자리가 1입니다.

그렇다는 것은 N-1 은 즉, X가 0인 경우의 수라는 겁니다.

그럼으로 N 의 경우의 수는 N-1 + N-2

라는 점화식이 도출되며

간단하게 풀면 됩니다.

다만, 항상 임계값에 대하여 테스트를 꼭 해주셔야 합니다!

int 로 풀 경우 범위값을 벗어나 버리기 때문에,

long 을 사용 하셔야 합니다!

항상 느끼는 거지만

dp는 규칙만 찾아내면

정말 코드는 짧고 간단하게 나오는 거 같은 느낌입니다 ㅎㅎ

코드

#include <iostream>
#include <vector>

using namespace std;


int main() {

	int n; 
	cin >> n; 

	vector<long long> dp;
	dp.push_back(1);
	dp.push_back(1);
	for (int i = 2; i < n; i++) {
		dp.push_back(dp[i - 1] + dp[i - 2]);
	}
	cout << dp[n - 1] ;
	
	return 0;
}