BOJ 백준 14855 만두 가게 사장 박승원

kyjdummy 2025. 4. 17. 20:13

문제 : https://www.acmicpc.net/problem/14855

[ 문제 요약 ]

간단히 말해, 밀가루의 총량이 주어지고, 밀가루 양 안에서 만두를 만들 때, 가장 크게 이득을 취할 수 있는 금액이 얼마인지를 묻는 문제

[ 테스트 케이스 설명 ]

10 2 2 1// 밀가루그램N(1<=1,000), 만두종류M(1<=10), 만두 속 없는 만두를 만드는데 드는 밀가루 그램(<=100), 만두속없는 만두 판매 비(<=100)
7 3 2 100// M개 줄에 해당 만두 속(A), 만두 하나에 필요한 만두속(B), 해당 만두에 들어가는 밀가루양(C), 해당 만두 판매비용 D(모두 1<=100)
12 3 1 10
만두 금액 합의 최댓값 : 241

[ 문제 해설 ]

코드는 2가지로 제공합니다.

처음 코드는 논리적으로 이해하기 쉽게 2차원 배열로 제시하고, 그 후 코드는 이를 더 최적화한 코드가 제시됩니다.

문제에서 입력이 너무 다양하게 많이 들어와 복잡할 수 있으나, 하나하나 뜯어 생각하면 간단합니다.

각 행마다 만두 속 총량과, 만두 하나를 만드는데 필요한 만두소가 따로 주어지는데 이건 두 변수를 “만들 수 있는 만두 개수”라는 개념으로 합칠 수 있습니다.

만들 수 있는 만두 개수 : 만두 속 총량 / 하나 만드는데 필요한 만두소

위 와 같이 하나의 변수로 생각하면, 맨 처음 주어지는, “만두 속없는 만두를 만드는 데 드는 밀가루 그램” 을 총 사용 가능한 밀가루

그램(N)과 나눠 만들 수 있는 만두 개수를 구해 놓을 수 있게 됩니다.

연산을 좀 더 편하게 하기 위해 node라는 별도의 자료 구조를 만듭니다.

class Node{
	int cnt, garu, cost;
	Node(int cnt, int garu, int cost){
		this.cnt	= cnt;	// 만들 수 있는 만두 개수
		this.garu	= garu;	// 하나 만들 때 들어가는 밀가루 양
		this.cost	= cost;	// 만두 하나당 얻을 수 있는 비용
	}
}

그리고 해당 만두 정보를 for 문으로 반복하면서, 얻을 수 있는 비용의 최댓값을 점차 증가해 나갑니다. dp 형태는 아래와 같습니다.

dp[만두 종류][밀가루 양] = 얻을 수 있는 최대 이익

여기서 생각해야 할 것이, 만두를 만드는 개수가 정해져 있기 때문에, 개수마다 반복문을 만들어 dp 값을 갱신해 주어야 합니다.

그리고 2차원 배열에서 dp를 실행하기 때문에,

새로운 만두 종류 탐색을 시작할 때마다 이전 만두 종류에서 구한 값을 현재로 복사해 와야 합니다.

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N		= Integer.parseInt(st.nextToken());		// 밀가루그램N(1<=1,000)
		int M		= Integer.parseInt(st.nextToken())+2;	// 만두종류M(1<=10), 연산 편의를 위해 +2 진행
		int G		= Integer.parseInt(st.nextToken());		// 만두 속 없는 만두를 만드는데 드는 밀가루 그램(<=100)
		int R		= Integer.parseInt(st.nextToken());		// 만두속없는 만두 판매 비(<=100)
		int dp[][]	= new int[M][N + 1];// 밀가루 그램에 따른 비용
		Node[] node = new Node[M];
		
		node[1] = new Node(N/G, G, R);
		
		for(int i=2; i<M; i++)
		{
			st = new StringTokenizer(br.readLine());
			// (모두 1<=100)
			int a = Integer.parseInt(st.nextToken());// 만두 속 총량
			int b = Integer.parseInt(st.nextToken());// 만두 하나에 필요한 만두속
			int c = Integer.parseInt(st.nextToken());// 해당 만두에 들어가는 밀가루양
			int d = Integer.parseInt(st.nextToken());// 해당 만두 판매비용
			// 만들 수 있는 만두 개수, 드는 밀가루양, 얻을 수 있는 판매 이익
			node[i] = new Node(a/b, c, d);
		}

		for(int m=1; m<M; m++)
		{
			for(int j=0; j<=N; j++)		// 새로운 행일 때 이전 값을 복사 
				dp[m][j] = dp[m - 1][j];
			
			for(int i=0; i<=N; i++)		// 밀가루 양을 돌면서 만들 수 있는 개수에 따른 최대 값 갱신
			{
				for(int c=1; c<=node[m].cnt; c++)// 만들 수 있는 개수
				{
					int nextGaru = i + node[m].garu * c;// 개수에 따라 산출되는 가루 양
					int cost = node[m].cost * c;	// 개수에 따라 얻을 수 있는 비용
					// 가루 양이 최대 값보다 클 때 스킵
					if(nextGaru > N)
						break;

					dp[m][nextGaru] = Math.max(dp[m][nextGaru], dp[m-1][i] + cost);
				}
			}
		}
		
		int ans = 0;
		// 마지막 행에 큰 값들이 다 들어가있으므로 가장 큰 것을 찾아 출력
		for(int i=0; i<=N; i++)
			ans = Math.max(ans, dp[M - 1][i]);
		
		System.out.print(ans);
	}
}
class Node{
	int cnt, garu, cost;
	Node(int cnt, int garu, int cost){
		this.cnt	= cnt;	// 만들 수 있는 만두 개수
		this.garu	= garu;	// 하나 만들 때 들어가는 밀가루 양
		this.cost	= cost;	// 만두 하나당 얻을 수 있는 비용
	}
}

[ 최적화 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N		= Integer.parseInt(st.nextToken());		// 밀가루그램N(1<=1,000)
		int M		= Integer.parseInt(st.nextToken())+2;	// 만두종류M(1<=10), 연산 편의를 위해 +2 진행
		int G		= Integer.parseInt(st.nextToken());		// 만두 속 없는 만두를 만드는데 드는 밀가루 그램(<=100)
		int R		= Integer.parseInt(st.nextToken());		// 만두속없는 만두 판매 비(<=100)
		int dp[]	= new int[N + 1];// 밀가루 그램에 따른 비용
		Node[] node = new Node[M];
		
		node[1] = new Node(N/G, G, R);
		
		for(int i=2; i<M; i++)
		{
			st = new StringTokenizer(br.readLine());
			// (모두 1<=100)
			int a = Integer.parseInt(st.nextToken());// 만두 속 총량
			int b = Integer.parseInt(st.nextToken());// 만두 하나에 필요한 만두속
			int c = Integer.parseInt(st.nextToken());// 해당 만두에 들어가는 밀가루양
			int d = Integer.parseInt(st.nextToken());// 해당 만두 판매비용
			// 만들 수 있는 만두 개수, 드는 밀가루양, 얻을 수 있는 판매 이익
			node[i] = new Node(a/b, c, d);
		}

		for(int m=1; m<M; m++)
		{
			for(int i=N; i>=0; i--)				// 중복 선택을 막기위해 밀가루 역순 탐색
			{
				for(int c=1; c<=node[m].cnt; c++)// 만들 수 있는 개수
				{
					int prevGaru = i - node[m].garu * c;// 이전 가루양
					int cost = node[m].cost * c;		// 개수에 따라 얻을 수 있는 비용
					// 가루 양이 음수가 되면 스킵
					if(prevGaru < 0)
						break;

					dp[i] = Math.max(dp[i], dp[prevGaru] + cost);
				}
			}
		}
		
		int ans = 0;

		for(int i=0; i<=N; i++)
			ans = Math.max(ans, dp[i]);
		
		System.out.print(ans);
	}
}
class Node{
	int cnt, garu, cost;
	Node(int cnt, int garu, int cost){
		this.cnt	= cnt;	// 만들 수 있는 만두 개수
		this.garu	= garu;	// 하나 만들 때 들어가는 밀가루 양
		this.cost	= cost;	// 만두 하나당 얻을 수 있는 비용
	}
}

dp 배열을 2차원에서 1차원으로 줄이고, 불필요한 복사 연산은 제거했습니다.
중복 연산을 피하기 위해 밀가루를 N부터 역순으로 탐색합니다. 그리고 현재 탐색 중인 밀가루 i를 이전 prevGaru 위치와 비교하며 최댓값을 갱신합니다.

[ 속도 차이 ]