백준 1049번: 기타줄 (JAVA)

 

문제 해석

 

N개의 줄이 끊어져 그만큼 줄을 사야하는데 6개 묶음의 패키지로 구매하거나 낱개로 구매하는 방법이 있다.

이 문제는

이 입력 예제를 이해하는 것 때문에 시간이 좀 걸렸다.

알고보니 패키지를 사용하여 필요한 줄 개수보다 많이 구매하더라도 낱개를 이용하여 개수를 맞춰 구매하는 것보다 싸면

패키지만 이용해서 구매하는 선택을 하는 것이었다.

 

알고리즘

 

이 문제에서 어느 브랜드는 패키지 가격이 어떻고 낱개 가격이 어떻고 복잡하게 생각할 필요 없이 한 브랜드를 여러번 구매할 수 있기 때문에 브랜드별 패키지 가격을 오름차순으로 정렬하고 브랜드별 낱개 가격을 오름차순으로 정렬하여 각각 제일 첫번째 브랜드들만 이용하면 된다.

줄을 구매하는 방법은 다음과 같다.

 

1. 패키지로만 사서 (필요 줄 개수보다 초과되더라도) 구매하는 방법

2. 낱개로만 구매하는 방법

3. 패키지로 살 수 있을만큼 사고 남은 필요 개수는 낱개로 채워 구매하는 방법

 

이 방법들을 모두 진행하여 가장 비용이 적게 드는 방법을 선택하면 된다.

 

코드