재시민

www.acmicpc.net/problem/1003

처음으로 풀어본 DP 문제

가끔 에브리타임 보면 DP 가 그렇게 어렵다고 하던데 도통 무슨 말인지 몰랐다.근데 오늘 알고리즘 수업을 듣고 한 번 복습 겸 문제를 풀어보았다.DP(Dynamic Programming) 즉, 동적 프로그래밍우리 교수님은 동적 프로그래밍이라는 말을 별로 달가워 하시지 않더라 ㅋㅋ

여튼 흔히 아는 피보나치 수열을 재귀함수로 표현하면 0.25 초내로 풀지 못한다.DP 배열을 선언해서 점화식 형태로 만들어 풀어주었다.처음에는 이상하게 만들어서 원하는 결과가 나오지 않았는데샤워하다가 영감이 떠올라 바로 작성했더니 실행이 되어 기분이 좋았다.

오늘 경험한 바에 따르면 DP 는 점화식 구현 같은 기분이 든다.아닐수도 있고 ^^백준을 이용하면서 랭킹 욕심에 하지도 않던 알고리즘 공부를 시작해 감회가 새롭다.랭킹시스템 덕분인 것 같다. 우리학교에서 짱먹고싶다.

#include <iostream>
using namespace std;

int dp[10000][2];
int fibo(int a) {
	dp[0][0] = 1;
	dp[0][1] = 0;
	dp[1][0] = 0;
	dp[1][1] = 1;
	if (a == 0) {
		return 0;
	}
	else if (a == 1) {
		return 0;
	}
	else {
		for (int i = 2; i <= a; i++) {
			dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
			dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
		}
	}
	return dp[a][0], dp[a][1];
}
int main(void) {
	int T;
	cin >> T;
	for (int i = 0;i < T;i++) {
		int N;
		cin >> N;
		fibo(N);
		cout << dp[N][0] << " " << dp[N][1] << '\n';
	}
	
	return 0;
}

dp[i][0], dp[i][1] 을 따로 선언해 초깃값을 선언하고 0이 나오는 횟수, 1이 나오는 횟수를 나누어 리턴했다.