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

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

예제 입출력

• 예제 입력 1
  18
• 예제 출력 1
  4
• 예제 입력 2
  4
• 예제 출력 2
  -1
• 예제 입력 3
  6
• 예제 출력 3
  2
• 예제 입력 4
  9
• 예제 출력 4
  3
• 예제 입력 5
  11
• 예제 출력 5
  3

Solution

DP를 쓰지 않았을 때

#include <iostream>

using namespace std;

int main(){
    int N;
    cin >> N;
    int answer = 0;
    while(N>=0){
        if(N%5 == 0) {
            answer += (N / 5);
            cout << answer << "\n";
            return 0;
        }
        N -= 3;
        answer += 1;
    }
    cout << "-1\n";
    return 0;
}

진짜 단순하다. 사실 데이터의 범위가 (3 ≤ N ≤ 5000) 인데 굳이 어렵게 DP씩이나 쓸 필요는 없다. 그냥 N을 입력받고 N이 0보다 크거나 같은 동안 5의 배수인지 아닌지를 생각 해 보면된다.
이 융통성이라곤 없는 상근이는 어떻게든 최대한 적은 봉지를 들고가기 위해 18키로의 설탕을 대충 3키로 6개에 집어넣든 5키로 3개 키로 1개에 집어넣든 아니면 5키로 4개에 집어넣든 하면 될 것이지 어떻게든 정확하게 봉투에 용량을 맞추려고 한다.
무슨 말이냐면 5로 나누어 떨어지거나, 나머지가 3의 배수여야 한다는 것이다. 그래서 일단은 3씩 깎아가면서 5로 나누어 떨어지는지를 계속 체크하면 된다.

만약 N 이 22라면 3으로도 5로도 나누어떨어지지 않으며, 나머지도 3으로도 5로도 나누어떨어지지 않는다. 가장 적은 수의 봉지를 써야 하기 때문에 5키로 기준으로 나누는 것.

간단히 풀면 이렇게 풀 수 있다. 그렇지만 재미없으니 DP를 써보도록 하자.

DP를 썼을 때

#include <iostream>
#define MAX 5001
using namespace std;
int dp[MAX]; 

int main() {
	int N;
	cin >> N;
	dp[3] = 1;
    dp[5] = 1;

	for (int i = 6; i <= N; i++) {
		if (dp[i - 3]) dp[i] = dp[i - 3] + 1;
		if (dp[i - 5]) dp[i] = dp[i] ? min(dp[i] , dp[i - 5] + 1) : dp[i - 5] + 1;
	}
	cout << (dp[N] == 0 ? -1 : dp[N]) << '\n';
	return 0;
}

우선 DP 테이블을 쭉 만든다. 최대로 들어올 수 있는 데이터 만큼.
그리고 3번 인덱스, 5번 인덱스에 각각 1씩 처리한다. 한 자루씩 일단 가능하다 생각 해 보는 것이다.
그 다음 i = 6부터 N까지 테이블을 채워나간다.

for (int i = 6; i <= N; i++) {
    if (dp[i - 3]) dp[i] = dp[i - 3] + 1;
    if (dp[i - 5]) dp[i] = dp[i] ? min(dp[i] , dp[i - 5] + 1) : dp[i - 5] + 1;
}

N이 11인 경우는 다음과 같다. DP테이블을 한번 출력 해 보았다. (0은 생략)

DP 테이블 인덱스가 3인 경우와 5인 경우에 초기 세팅처럼 1씩 들어간다. 그 이후로 6부터 쭉 진행하면서 3, 5이전에 각각 값이 존재하는지 체크 후 값을 갱신 해 나간다. i값은 N까지 증가하는데, 설탕의 무게가 점점 증가하며 N까지 진행되고 가능한 경우의 수를 DP 테이블에 저장한다고 생각하자.

if (dp[i - 3]) dp[i] = dp[i - 3] + 1;

dp[i-3] 에 값이 존재한다면 dp[i]를 dp[i-3] +1 로 업데이트 시킨다. (3키로 봉지 추가)

if (dp[i - 5]) dp[i] = dp[i] ? min(dp[i] , dp[i - 5] + 1) : dp[i - 5] + 1;

dp[i-5] 에 값이 존재한다면 dp[i] 에 값이 없다면 dp[i-5] + 1로 업데이트, 아니면 dp[i]와 dp[i-5]+1를 비교해서 더 작은 값을 업데이트한다. 즉 기존의 값 보다 5키로를 더한 값이 더 적다면 그 값을 업데이트 하는 것이다.
i = 6인 경우는 i = 3인 경우를 보고 그대로 + 1 처리 된다. 그렇지만 i = 8인 경우엔 i = 5인 경우와 i = 3인 경우 두가지를 비교하게 된다. 5키로 봉투가 하나 있는 경우와, 3키로 봉투만 있는 경우. 두 경우 다 if문에 걸리므로 최종적으로 가장 작은 경우가 저장된다.

DP연습용으로 좋은 문제라고 생각한다. 역시DP는 참...어렵다.