#2839 : 설탕 배달

풀이방법

사용된 것:

다이나믹 프로그래밍(DP)

수학(방정식)

그리디 알고리즘

 

이 문제의 여러가지 해법 중,

다이나믹 프로그래밍으로 푸는 방법과

5000 이하의 모든 자연수 $n$에 대하여 $5x + 3y = n$을 푸는 방법

두 가지로 풀어보았다.

 

 

 

2022.03.24(1)

다이나믹 프로그래밍으로 푸는 방법이다.

 

모든 자연수는 다음의 네 가지 경우 중 하나이다.

 

1. 3의 배수와 5의 배수의 합으로 만들어진 수에 5를 더하여 도출됨
2. 3의 배수와 5의 배수의 합으로 만들어진 수에 3을 더하여 도출됨
3. 1번과 2번 모두 가능함
4. 1번과 2번 중 어떤 것도 불가능함

따라서,

길이가 5001인 1차원 정부 배열 dp를 만들어서

초기의 값들만 다음과 같이 정의해두고

dp[0] = -1;

dp[1] = -1;

dp[2] = -1;

dp[3] = 1;

dp[4] = -1;

dp[5] = 1;

 

다음과 같이 두 개의 조건문으로 이루어진 반복문을 6부터 5000까지 돌려주면 된다.

		for(int i = 6; i<5001; i++) {
			dp[i] = -1;
			if(dp[i-3] != -1) dp[i] = dp[i-3]+1;
			if(dp[i-5] != -1) dp[i] = dp[i-5]+1;
		}

만약 i가 두 개의 조건문 중 어느 것에도 해당되지 않는 수라면

1. 3의 배수와 5의 배수의 합으로 만들어진 수에 5를 더하여 도출됨
2. 3의 배수와 5의 배수의 합으로 만들어진 수에 3을 더하여 도출됨
3. 1번과 2번 모두 가능함
4. 1번과 2번 중 어떤 것도 불가능함

4번에 해당되는 것이므로 dp[i]에 -1이 저장된다.

 

만약 i가 두 개의 조건문 모두에 해당되는 수라면

1. 3의 배수와 5의 배수의 합으로 만들어진 수에 5를 더하여 도출됨
2. 3의 배수와 5의 배수의 합으로 만들어진 수에 3을 더하여 도출됨
3. 1번과 2번 모두 가능함
4. 1번과 2번 중 어떤 것도 불가능함

3번에 해당되는 것이다.

이 경우, 3킬로그램 봉지를 많이 옮기는 것보다 5킬로그램 봉지를 많이 옮기는 것이 봉지 개수를 최소로 만드므로,

3이 아닌 5에 대한 조건문에 의해 최종 dp[i]의 값이 정해져야 한다.

이를 위해,

본 코드에서처럼 5에 대한 조건문을 더 나중에 수행하도록 하거나,

if else문을 이용해 5에 대한 조건문에서 참으로 판별되지 않았을 경우에만 3에 대한 조건문에 투입되도록 코드를 짜야 한다.

 

 

 

 

 

 

 

 

 

 

2022.03.24(2)

미지수가 두 개인 방정식을 풀어 해결하는 방법이다.

 

길이가 5001인 1차원 정수 배열 arr를 만든다.

 

arr[3]부터 arr[5000]까지 다음의 과정을 수행해야 한다.

 

3부터 5000까지의 자연수 $i$에 대하여,
$5x + 3y = i$
을 만족하는 자연수 $x$와 $y$를 구하되,
이 방정식을 만족하는 $(x, y)$의 순서쌍이 여러 개라면 $x$의 값이 가장 큰 것으로 선택한다.
가장 무거운 5킬로그램짜리 봉지를 가능한 많이 배달해야, 상근이가 배달하는 봉지의 개수가 최소가 되기 때문이다.

이렇게 알맞은 $x$와 $y$를 구했다면 arr[i]에 $x + y$를 저장한다.
위의 방정식을 만족하는 $x$와 $y$가 없다면 arr[i]에 -1을 저장한다.

 

코드로 구현하는 방법은 다음과 같다.

 

주어진 수가 $n$, 즉

$5x + 3y = n$

을 풀어서 dp[n]을 채워야 하는 상황이라고 하자.

 

먼저, 만약 n이 5의 배수라면 dp[n]에 n/5의 값을 넣고 끝낸다.

 

그렇지 않다면 다음과 같이 한다.

1000부터 1까지 $x$의 값을 1씩 줄여간다.

$5x$가 n보다 작을 때까지 계속 줄인다.

$5x$가 n보다 작아졌다면,

$n - 5x$가 3의 배수인지 확인한다.

 

$n - 5x$가 3의 배수라면 최적의 해를 찾은 것이다.

즉시 arr[n]에 $x + y$를 저장한다.

 

$n - 5x$가 3의 배수가 아니라면, $x$를 또 1만큼 줄이고 위의 밑줄 친 부분을 다시 해본다.

 

$x$가 0이 될 때까지 $n - 5x$가 3의 배수인 경우가 존재하지 않았다면 arr[n]에 -1을 저장한다.

 

코드

java(2022.03.24(1))

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int[] dp = new int[5001];
		
		dp[0] = -1;
		dp[1] = -1;
		dp[2] = -1;
		dp[3] = 1;
		dp[4] = -1;
		dp[5] = 1;
		
		//dp 배열 만들어두기
		for(int i = 6; i<5001; i++) {
			dp[i] = -1;
			if(dp[i-3] != -1) dp[i] = dp[i-3]+1;
			if(dp[i-5] != -1) dp[i] = dp[i-5]+1;
		}
		
		//정답 출력
		System.out.print(dp[Integer.parseInt(br.readLine())]);
	}

}

java(2022.03.24(2))

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int[] arr = new int[5001];
		
		//arr 배열 만들어두기
		for(int i = 3; i<5001; i++) {
			arr[i] = -1;	//arr[i]의 초기값은 -1
			
			if(i%5 == 0) {arr[i] = i/5; continue;}
			
			//미지수가 2개인 방정식 풀기
			for(int j = 1000; j>=0; j--) {
				if(5*j <= i) {
					if((i - (5*j)) % 3 == 0) {
						//올바른 해를 찾아냈다면 arr[i]의 값을 변경하고 반복문을 종료한 뒤 다음 i로 진행
						arr[i] = j + ((i - (5*j)) /3);
						break;
					}
				}
			}
		}
		
		//정답 출력
		System.out.print(arr[Integer.parseInt(br.readLine())]);
	}

}