이것 저것 &

카카오 코드 페스티벌  의 카카오 코드 페스티벌 2018 예선 A번 문제입니다. 

간단한 프로그래밍 문제입니다. 

#include <iostream>
using namespace std;
int t = 0, a = 0, b = 0, result = 0;
void festival1(int num) {
	if (num == 1)
		result += 5000000;
	else if (num <= 3)
		result += 3000000;
	else if (num <= 6)
		result += 2000000;
	else if (num <= 10)
		result += 500000;
	else if (num <= 15)
		result += 300000;
	else if (num <= 21)
		result += 100000;
}
void festival2(int num) {

	if (num == 1)
		result += 5120000;
	else if (num <= 3)
		result += 2560000;
	else if (num <= 7)
		result += 1280000;
	else if (num <= 15)
		result += 640000;
	else if (num <= 31)
		result += 320000;
}
int main() {
	cin >> t;

	while (t--) {
		result = 0;
		cin >> a >> b;
		if (a != 0)
			festival1(a);
		if (b != 0)
			festival2(b);
		cout << result << endl;
	}
	
}

전형적인 dp문제입니다.

반복문으로 arr배열을 탐색하면서 

자신보다 arr값이 작고 dp값이 가장큰 값에 자신의 arr값을 더한값이 dp값이 되는 점화식입니다. 

즉 , dp[i] = arr[i] + dp[maxed_index]의 형태가 됩니다.

전체코드입니다:)

#include <iostream>
using namespace std;

int n, result = 0;
int arr[1001] = { 0 };
int dp[1001] = { 0 };


int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) 
		cin >> arr[i];
	
	for (int i = 1; i <= n; i++) {
		int maxed = 0,maxed_index=0;
		for (int j = i - 1; j >= 1; j--) {
			if (arr[j] < arr[i] && maxed < dp[j] )
				maxed = dp[j], maxed_index = j;
		}
		dp[i] = arr[i] + dp[maxed_index];
		if (result < dp[i]) result = dp[i];
	}

	cout << result << endl;
}

쉬운 dp 문제입니다.

P(1)부터 P(11)까지 첫 11개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16 ... 

 dp[n] = dp[n-1] + dp[n-5] 라는 점화식을 찾을 수 있게 됩니다.

정답률이 30%대라는게 믿기지 않을 정도로 쉬워서 의아하며, 

ㅋㅋㅋㅋㅋㅋㅋㅋ

한번 틀렸습니다. 숫자가 증가함에 따라 기하급수적으로 수가 커지는거를 신경못썻습니다. 

int형은 4byte = 32bit = 2의 32승

즉 2,147,483,648x2 만큼의 수를 저장할 수 있습니다.

음수,0양수 모두를 포함해야하기 때문에 아래 표와 같은 범위의 수를 표현할 수 있게 됩니다.

수가 넘어갈때는 제일 아래의 음수값 - 2,147,483,648로 내려가 1씩 올라가며 출력을 하는 구조입니다.

저는 c++에서 long long 형을 사용하여 문제를 해결하였습니다. 

정답코드

#include <iostream>
using namespace std;

long long dp[101] = { 0 };
int t = 0, n;
int main() {
	dp[1] = 1, dp[2] = 1, dp[3] = 1, dp[4] = 2;
	for (int i = 5; i <= 100; i++)
		dp[i] = dp[i - 1] + dp[i - 5];

	cin >> t;

	while (t--) {
		cin >> n;
		cout << dp[n] << endl;
	}
}

실패코드를 먼저 보여드립니다.

#include <iostream>
#include <cmath>
using namespace std;
int dp[100001] = { 0 };

int main() {
	int n = 0;
	cin >> n;
	dp[0] = 0, dp[1] = 1, dp[2] = 2;

	for (int i = 3; i <= n; i++) {
		int num = pow(i,0.5);
		dp[i] = 1 + dp[i - num*num];
		cout << dp[i] << endl;
	}
	cout << dp[n] << endl;
}

반례가 있습니다.

12 = 3*2 + 1 + 1 + 1 = 4

12 = 2*2 + 2*2 + 2*2 = 3

명백하게 그리디적인 관점에서 문제를 해결나갈 수 없는 것을 보실 수 있습니다.

즉, 제곱값이 자신보다 작은 모든 제곱근들에서의 경우의 수를 비교해주어 결과값을 도출하여야 하는 문제입니다. 

#include <iostream>
#include <cmath>
using namespace std;
int dp[100001] = { 0 };

int main() {
	int n = 0;
	cin >> n;
	dp[0] = 0, dp[1] = 1, dp[2] = 2;

	for (int i = 3; i <= n; i++) {
		int num = pow(i,0.5);
		dp[i] = 1 + dp[i - num*num];
		for (int j = num-1; j >= 1; j--) {
			if( (1 + dp[i - j*j]) < dp[i] )
				dp[i] = 1 + dp[i - j*j];
		}
	}
	cout << dp[n] << endl;
}

전형적인 dp문제입니다.

점화식을 고려할때 머리로 연상되지 않습니다.

표를 그리며 차근차근 풀어나가보았습니다.  

예시입력에 경우
        k   0   1   2   3   4   5   6   7   8   9   10
c(0)    [0] 1   0   0   0   0   0   0   0   0   0   0
c(1)    [1] 1   1   1   1   1   1   1   1   1   1   1
c(2)    [2] 1   1   2   2   3   3   4   4   5   5   6
c(3)    [5] 1   1   2   2   3   4   5   6   7   8   10

1의 경우에는 모두 1가지 경우의수를 가지게 되고

2를 포함할 경우 2의 배수마다 경우가 한가지씩 증가하는 것을 확인 할 수 있었습니다.

즉, 2를 포함할 때 1의 경우+ DP[N-2] + 1 의 경우가 됨을 확인할 수 있습니다. 

5를 포함할 때에는 (1의경우가 포함된) 2의 경우 + DP[N-5] + 1 이 됨을 확인할 수 있었습니다. 

즉 점화식을 나타내면 

for (int i = 0; i < n; i++) {
		dp[i][0] = 1;
		int num = arr[i];
		for (int j = 1; j <= k; j++) {
			if (j >= num&& i>0) dp[i][j] = dp[i][j - num] + dp[i - 1][j];
			else if(i>0) dp[i][j] = dp[i - 1][j];
			else if (j >= num) dp[0][j] = dp[i][j - num];
		}

	}

네 메모리 초과입니다.. :) ㅋㅋㅋ

문제조건이 4MB였네요. 

int형은 4byte이고 n=100까지, k=10000까지이니 dp 2차원 배열은 4000,000byte= 4000kbyte = 4mbyte이므로 메모리 초과가 나는것입니다. 직관적으로 점화식이 변화하는것을 확인했기때문에 dp[101][10001] 를 dp[10001]로 줄여보겠습니다. 

	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		int num = arr[i];
		for (int j = 1; j <= k; j++) {
			if (j >= num) dp[j] += dp[j - num] ;
		}
	}

전체코드입니다. 

#include <iostream>

using namespace std;

int dp[10001] = { 0 };
int n = 0, k = 0;
int arr[100] = { 0 };
int result = 0;

int main() {

	cin >> n >> k;
	
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	
	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		int num = arr[i];
		for (int j = 1; j <= k; j++) {
			if (j >= num) dp[j] += dp[j - num];
		}

	}
	cout << dp[k] << endl;
}