뚝딱뚝딱

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

💡 기타줄

Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.
끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

[입력]
첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

[출력]
첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

✅ 문제 풀이

• 일단 세트 가격과 낱개 가격의 최소 값을 각각 저장하는 변수를 지정한다.
• 입력을 받을 때마다 현재의 최소값과 비교하면서, 세트와 낱개의 각각 최소값을 구한다.
• 기타줄 개수인 N을 6으로 나누었을 때 나머지가 존재하면 그 몫보다 1 큰 만큼을 최소 세트값과 곱한 값, N만큼을 낱개로만 샀을 때의 값, N을 6으로 나누었을 때의 몫 만큼을 최소 세트값과 곱한 값+6으로 나눈 나머지에 최소 낱개값과 곱한 값을 더한, 이 세가지 결과 중 가장 작은 경우가 이 문제의 최종 답이 된다.

✏ 코드 전문

#include<iostream>
#include<algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	int smin = 1000;
	int omin = 1000;
	for (int i = 0; i < M; i++) {
		int s, o;
		cin >> s >> o;

		smin = min(smin, s);
		omin = min(omin, o);
	}

	int base = smin * (N / 6);
	int temp = min((N%6==0) ? base : base + smin, base + (N % 6)*omin);
	cout << min(omin * N, temp);

	return 0;
}

• base의 경우 N이 6의 배수로써 딱 떨어질 수 있고, 나머지가 있을 수 있음.
• 따라서 세트로만 살 경우에서는, 만약 N이 6배수이면 base 그대로 계산하고, 나머지가 존재한다면 +1하여 계산하도록 하였음.
• min함수는 인자를 두개만 받으므로, 세개를 비교하기 위해 두개를 먼저 비교하고 그 결과를 cout으로 바로 나머지 하나와 함께 비교하여 출력하도록 하였음.