[백준 / BOJ] 8901 화학 제품

문제

출처 : www.acmicpc.net/problem/8901

8901번: 화학 제품

상근이는 세 종류의 화학물질 A, B, C를 가지고 있다.

화학물질을 AB, BC, CA로 조합해서 세가지 제품을 만들수있는데, 

A,B,C의 갯수와 AB,BC,CA의 가격이 주어졌을때, 상근이가 얻는 최대이익을 출력하는 문제다.

 

풀이

완전탐색으로 풀리는문제다. 하지만, 그냥 모든경우를 봐줄경우,

1000 * 500 * 250 * 250 ?? 처럼 나와서 시간초과가 난다.

 

한가지 제품을 만드는 경우를 미리 정해주면, 두가지 제품으로는 최대이익을 얻는경우를 바로 알수있다.

 

예를들어, 

A = 5, B = 3, C = 7

AB = 100, BC = 30, CA = 80으로 주어졌다고 하자, 

 

1. AB제품을 한가지도 안만들었을때,

이때, 사용할수있는 화학물질은A = 5, B = 3, C = 7 이다.

제품 AB는 앞에서 봐줬으므로, BC와 CA를 봐준다. BC와 CA를 가지고 최대한 얻을수있는 이익은

둘중 비싼가격을 가진 제품을 먼저 최대한 만들고 남은 물질들을 가지고 싼 가격을 가진 제품을 만드는것이다.

위 경우는 100 * 0 + 80 * 5 + 30 * 2 가 될것이다. (AB제품 0개 CA제품 5개 BC제품 2개)

 

2.AB제품을 한가지 만들었을때,

이때, 사용할수있는 화학물질은A = 4, B = 2, C = 7 이다.

1번과 마찬가지로 하면

100 * 1 + 80 * 4 + 30 * 2 이 된다.

 

위 과정을 AB = 0 부터 AB를 최대로 만들수있을때 까지 반복해주면 된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/8901%20%ED%99%94%ED%95%99%20%EC%A0%9C%ED%92%88/main.cpp

devxb/JJUNalgo