백준 2502 - 떡 먹는 호랑이(다이나믹 프로그래밍)

 

DP에 대해 한번 정리를 하고 싶어 DP문제를 찾아서 풀어보았다.

DP에 대한 개념부터 한번 정리하겠다.

 

Dynamic Programming

동적계획법의 정의는 하나의 큰 문제를 여러개의 작은 문제로 나누어 해결하는 것이다.

나는 이러한 정의가 분할정복과 크게 차이가 없다고 느껴져, 반복되는 부분의 결과를 써 놓아 기억하고, 활용하기라고 생각하고있다.

 

DP 예시

 

DP를 활용했을때 시간복잡도적으로 이득을 볼 수 있는 가장 대표적인 예시가 피보나치수열이다.

피보나치 수열은 F(0) = 0, F(1) = 1, F(N) = F(N-1)+F(N-2)인 수열이다

 

피보나치 수열 구현 코드

재귀를 통한 구현이다.

가장 기본적인 아이디어로, 위의 수식을 그대로 코드로 구현한 것을 확인할 수 있다. Top-Down방식으로 값을 찾아나간다.

int fibo(int num)
{
	if(num == 0)
		return 0;
	if(num == 1)
		return 1;
	return fibo(num-1) + fibo(num-2)
}

 

반복을 통한 구현이다. 재귀와 달리 Bottom Up 방식으로 값을 만들어 나간다.

vector<int> vt;
int fibo(int num)
{
	vt.push_back(0);
	vt.push_back(1);
	for(int i = 2; i < num; i++)
		vt.push_back(vt[i-1]+vt[i-2]);
	return vt[vt.size()-1];
}

 

그림으로 이해하는 피보나치

 

아래의 그림을 통해 Top-Down 방식에서 bottom Up방식으로 바꿈으로써 반복을 매우많이 줄일 수 있는것을 확인 할 수 있다.

 

피보나치 결론

 

핵심은 어떠한 방식으로 구현했느냐가 아니라, 이전에 사용한 정보를 재사용해 반복적인 계산을 줄이는 것이다.

예를 들어 f(3)을 이미 구해놓았으면 그 정보를 기억해 다시 f(3)을 만났을때 f(2)와 f(1)을 보지 않고 바로 이미 구한 f(3)의 값을 사용하는것이 핵심이다.

 

백준 2502

문제 해결 과정

 

N이 주어졌을때 f(N)을 구하는것이 일반적인 피보나치 문제라면, 이 문제에서는 f(N)과 N이 주어졌을때 초기값 f(1), f(2)를 찾는 문제이다.

우선 먼저 가장 기초적인 완전탐색을 생각해보았다.

f(1) < f(2)의 조건에서 초기값의 범위는 따로 주어져있지 않지만 f(N)이 100000 이하이므로 모든 초깃값의 경우는 약 100000 * 50000개가 될 것이다. (1일차, 2일차의 모든 경우의 수) 이는 당연히 터지므로 불가능하다.

두번째로 DP를 통해 해결하는 아이디어를 생각해보았다.

1일차를 a라고 두고 2일차를 b라고 두었을때 3일차는 a+b, 4일차는 a+2b가 될 것이다.

이를 반복하면 n일차일때 xa+yb라는 수식을 구할 수 있다.

그렇다면 우리는 x와 y의 값을 알고 있기때문에 a와 b도 구할 수 있지 않을까 ? 라고 생각하였다.

예를들어 6일차에 떡이 41개라는 입력이라고 가정하자. 6일차에 3a+5b이다. 그렇다면 3a + 5b = 41의 해를 구하면 되는것이다.

 

내가 고민했던 부분은, 처음에 a의 경우가 10만개고 b의 경우도 10만개라서 불가능해 보였다.

하지만 a를 고정시켜 놓으면 5*b로 우항을 나누어봐서 값이 떨어지는지 유무로 유효한 a인지를 체크할 수 있다는 아이디어가 생각나 해결할 수 있었다.

 

구현 코드

 

결국 두가지 과정을 통해 해결한다. 

1. 날짜에 따른 a, b가중치 구하기

void makeWeight()

{

weightAr[1][0] = 1;

weightAr[2][1] = 1;

for(int i = 3; i <= 30; i++)

{

weightAr[i][0] = weightAr[i-1][0] + weightAr[i-2][0];

weightAr[i][1] = weightAr[i-1][1] + weightAr[i-2][1];

}

}

2. 가중치에 따른 a, b구하기

void findAnswer(int w1, int w2)

{

int i = 1;

while(1)

{

int aValue = w1 * i;

int left = K-aValue;

if(left % w2 == 0)

{

cout << i << endl;

cout << (K-aValue) / w2 << endl;

break;

}

i ++;

}

}

DP개념이 많이 들어가지는 않았지만, bottom-up을 사용해 문제를 해결할 수 있었다.