[백준] 1049번: 기타줄 [C++]

 

알고리즘 분류: 수학, 그리디 알고리즘

문제 링크: https://www.acmicpc.net/problem/1049

1049번: 기타줄

 

 

 

 

【 풀이 】

 

그리디 알고리즘 기초 문제이다.

결국 문제에서 요구하는 것은 6개짜리 패키지의 가격과 낱개의 가격들을 입력받았을 때

어떤 조합으로 사야 최솟값으로 끊어진 기타줄을 바꿀 수 있는지이다.

최솟값을 구할 수 있는 아이디어는 세가지이다.

1. 6개 패키지 중에서 가장 최솟값인 패키지로만 기타줄을 샀을 때(N 초과해도 무관)
2. 낱개 중에서 가장 최솟값으로만 기타줄을 샀을 때
3. 최솟값 패키지 + 최솟값 낱개

 

 

 

 

【 코드 】

 

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

enum {
	ONLY_PACKAGE	= 0,
	ONLY_PIECE	= 1,
	TOGETHER	= 2,
};

int main() {
	int N, M;
	cin >> N >> M;
	
	int cnt = N / 6;

	int result[3];
	int P_package_6[51];
	int P_piece[51];

	int Package_min	= 1001;
	int Piece_min	= 1001;

	for (int i = 0; i < M; i++) {
		cin >> P_package_6[i] >> P_piece[i];

		if (Package_min > P_package_6[i])
			Package_min = P_package_6[i];
		if (Piece_min > P_piece[i])
			Piece_min = P_piece[i];
	}
	
	result[ONLY_PACKAGE]	= Package_min * (cnt+1);
	result[ONLY_PIECE]	= Piece_min * N;
	result[TOGETHER]	= (Package_min * cnt) + (Piece_min * (N%6));

	cout << *min_element(result, result + 3);

	return 0;
}