[BOJ] 1049 기타줄

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

Note

최대 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;
}

2019-01-16 13:00:00에 Tistory에서 작성되었습니다.