Baekjoon 1049 기타줄

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

소스결과 1984 KB / 0 ms

출처 Baekjoon

언어 C++ 17

분류 그리디 알고리즘

 

설명

최대 100줄짜리 기타를 치시거나 6현 기타 17개를 동시에 치실줄 아시는 세계적인 기타 플레이어 김지민씨가 새로운 줄을 사거나 교체 해야할 때

가장 싸게 사면 얼마에 살 수 있는지 대신 계산해주는 코드를 작성하자

 

경우는 크게 2개로 나눌 수 있다.

1. 낱개 가격으로 6개를 사는게 패키지보다 가격이 싼 경우

2. 패키지로 사는게 더 싼 경우

 

따라서 2가지 경우의 최소 값만 구하면 된다.

배열 전체를 저장하지 않아도 된다. 패키지 가격의 최소값과, 낱개 가격의 최소 값만 구하면 된다.

6개가 넘어가는 경우를 먼제 구한후 나머지 줄 수에 맞춰서 패키지를 사는게 좋을지 낱개로 사는게 좋을지 구분해서 값을 추하면 된다.

 

알고리즘

1. m개의 패키지 가격과 낱개의 가격을 입력 받는다.

2. 각각의 입력에 대해서 낱개 * 6개 의 가격과 패키지 가격 중 작은 값을 패키지 가격으로 설정한다.

3. 설정된 패키지 가격을 기준으로 최소 패키지 가격과 비교해 더 작은 값으로 갱신한다.

4. 낱개 가격 또한 최소 낱개 가격과 비교해 더 작은 값으로 갱신한다.

5. n을 6으로 나눈 몫 에 최소 패키지 가격을 곱한 값을 결과값 변수인 cost에 더한다.

6. 나머지 * 최소 낱개 값과 최소 패키지 가격을 비교해 더 작은 값을 cost에 더한다.

7. 결과 값 cost에 출력한다.

 

소스코드

#include <iostream>

using namespace std;

int main()
{
	int n, m;
	int minSixPieceOrPackage = 1001, minPiece = 1001;
	int cost = 0;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int pack, piece;
		cin >> pack >> piece;

		if (minPiece > piece)
			minPiece = piece;

		pack = piece * 6 < pack ? piece * 6 : pack;

		if (minSixPieceOrPackage > pack)
			minSixPieceOrPackage = pack;
	}

	cost = (n / 6) * minSixPieceOrPackage;
	int remain = n % 6;
	
	if (remain)
	{
		if (minSixPieceOrPackage < (minPiece * remain))
			cost += minSixPieceOrPackage;
		else
			cost += remain * minPiece;
	}

	cout << cost;

	return 0;
}