[1049] 기타줄

간단한 그리디 문제입니다.

처음에는 한 곳의 브랜드를 선택하면 그 곳만 선택해야 하는지 알았지만 질문들을 찾아보니 다른 브랜드끼리 선택해도 되는 거였습니다.

따라서 3가지 경우를 생각하면 됩니다.

1. 묶음으로 다 사기
2. 묶으로 살 수 있는 만큼 사고 단품으로 사기
3. 단품으로 다 사기

따라서,

- 묶음으로 살 경우의 최솟값(Sum_min)

- 단품으로 살 경우의 최솟값(piece_min)

에 대한 변수를 선언하고 이것을 토대로 계산을 진행하면 됩니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int n, m;
int sum_min = ~(1 << 31);
int piece_min = ~(1 << 31);
int min = ~(1 << 31);

void input() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		if (a == 0 || b == 0) { // 0이 나오면 최솟값은 0이되고 다 구해지게 됩니다.
			sum_min = 0;
			piece_min = 0;
			break;
		}
		sum_min = sum_min > a ? a : sum_min; // 묶음 최소값
		piece_min = piece_min > b ? b : piece_min; // 단품 최소값
	}
}

void solve() {
	if (sum_min == 0 || piece_min == 0) {
		printf("0");
		return;
	}
	int remain = n % 6;
	int a = (n / 6+1) * (sum_min); // 1번 경우
	int b = n / 6 * sum_min + remain * piece_min; // 2번 경우
	int c = n * piece_min; // 3번 경우
	min = min > a ? a : min;
	min = min > b ? b : min;
	min = min > c ? c : min;
	printf("%d", min);
}

int main(void) {
	input();
	solve();
} 

 

문제

1049번: 기타줄