1) 백준 2839 - 설탕 배달

<문제>

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

두 가지 방법으로 풀었다. (사실 그리디로 풀려다가 다 풀고 보니 DP 였던....ㅠㅠㅠ)

원래 그리디를 사용하려고 했으니까 그리디로 먼저 설명을 하자면!!!!

 

<코드 1>

#include <iostream>

using namespace std;

int main(void) {
	int N;
	cin >> N;
	
	int cnt_5 = N/5;	
	
	while(cnt_5 >= 0) {
		int n = N;
		n -= cnt_5*5;
		if(n % 3 == 0){
			cout << cnt_5+n/3;
			break;
		}
		cnt_5--;
	}
	if(cnt_5 == -1) {
		cout << -1;
	}
	
	return 0;
}

 - 설명

그리디의 성격을 생각해보면 간단하게 알 수 있는 문제다. 

5kg 또는 3kg만 사용이 가능하므로 더 큰 무게인 5kg을 기준으로 한다.

배달할 수 있는 5kg의 최대 갯수를 cnt_5로 선언해줬다.

후에 배달 가능한 5kg의 무게를 배달하고자 했던 무게에서 빼준다.

이 무게를 다시 3kg만 사용하여 배달할 수 있는지 확인해준다.

만약 가능하면 그냥태로 사용한 개수의 합을 더해줘서 출력을 해주고 break를 걸어준다.

불가능하다면 cnt_5를 하나씩 줄여가면서 계속 확인해준다.

 

그런데 cnt_5가 -1이 되버리면 배달이 불가능한 무게이므로 -1을 출력해주면 된다.

 

큰 것부터 점차 줄여나간다고 보면 될 듯싶다.

 

<코드 2>

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
	int N;
	cin >> N;
	
	int sweet[5001] = {0, -1, -1, 0, };
	
	for(int i = 3; i <= N; i++) {
		sweet[i] = i;
		if(i % 3 == 0) {
			sweet[i] = i/3;
		}
		if(i % 5 == 0) {
			sweet[i] = i/5;
		}
		for(int j = 1; j <= i/2; j++) {
			if(sweet[j] != -1 && sweet[i-j] != -1){
				sweet[i] = min(sweet[i], sweet[j]+sweet[i-j]);
			}
		}
		if(sweet[i] == i) {
			sweet[i] = -1;
		}
	}
	
	cout << sweet[N];
	
	return 0;
}

 - 설명

DP의 기술 중 메모이제이션을 사용했다.

1kg과 2kg은 배달이 불가능하므로 -1로 설정.

3kg부터 Nkg까지의 무게('i'로 선언)를 차례대로 하나씩 배열에 넣어준다.

 

예로 설명을 해보자. 3kg부터 차례대로 채우다가 8kg을 배열에 넣을 차례가 왔다고 가정하자.

i = 1	2	3	4	5	6	7
-1	-1	1	-1	1	2	-1
i = 7	6	5	4	3	2	1
-1	2	1	-1	1	-1	-1
total = -1	-1	2	-1	2	-1	-1

첫 번째와 세 번째 줄은 배열 index값이고, 두 번째와 네 번째 줄은 배열의 index에 들어있는 값이다.

그리고 마지막 줄은 그 둘을 합친 값이다.

우선 설명 전에 조건이 있다.

1. 둘 중 하나의 배열의 값이 -1이 있으면 그냥 넘어감.

2. index가 8kg / 2가 될 때까지만( 넘어가면 같은 계산만 한번 더하는 꼴이 돼버린다. - 시간낭비)

 

sweet [8]을 구하기 위해서

초기 sweet [8]을 8로 설정.

sweet [1] + sweet [7]를 해주고 sweet [8]과 더 작은 값을 sweet [8]에 넣어둔다. (sweet [8] = 8) // sweet[1]과 sweet[7] 둘 다 -1 이므로 계산하지 않음.

sweet [2] + sweet [6]을 해주고 sweet [8]과 더 작은 값을 sweet [8]에 넣어둔다. (sweet [8] = 8) // sweet [2]가 -1 이므로

계산하지 않음.

sweet [3] + sweet [5]을 해주고 sweet [8]과 더 작은 값을 sweet [8]에 넣어둔다. (sweet [8] = 2) // sweet [3], sweet [5]둘다 1.

sweet [4] + sweet [4]을 해주고 sweet [8]과 더 작은 값을 sweet [8]에 넣어둔다. (sweet [8] = 2) // sweet [4]가 -1 이므로

계산하지 않음.

 

최종적으로 sweet [8]에 들어있는 값은 2가 된다. 만약에 최종적으로 sweet [i] = i 라면, sweet [i]에 -1을 넣어주도록 하자.

 

이런 방법으로 하나씩 메모해둔다. 결국, sweet이라는 배열에 들어있는 값들은 그 경우의 최솟값이 되므로 그중에서도 최솟값을 찾아주면 된다.

(..... 설명 어려워.... ㅠㅠㅠㅠ)

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

그리디로 풀면 저래 간단한데...ㅠㅠㅠ

적절히 필요한 알고리즘을 잘 쓰는 연습을 해야겠다.