BOJ) 기타줄

기타줄

1049번: 기타줄

풀이

 

첫째 줄에 갈아야하는 기타 줄의 수 n과 기타줄 브랜드 수 m이 공백을 두고 주어진다.

다음 m줄에 대해서 각 브랜드의 기타줄 패키지 가격과 1개의 가격이 차례대로 주어진다.

이 때, 기타줄을 갈 수 있는 최소 가격을 구하는 문제다.

 

dfs로 dp로 할까 생각하다가 dfs로 먼저 짜봤다. 하지만, n이 최대 100이어서 빠르게 손절했다. (가지치기를 한다해도 비효율적)

다음은 dp를 생각했다. 줄 하나를 갈 때, 2개를 갈 때, ... n개를 갈 때 가격을 다 저장하려고 했는데 이것도 비효율적인 것 같았다.

 

그래서 브랜드 별로 패키지 가격과 줄 가격을 입력받을 때, 각각 최소값을 저장해서 답을 구하기로 했다.

패키지 가격의 최소값 packageCost 와 기타줄 하나 가격의 최소값 stringCost에 값을 저장해서 solution으로 넘겨줬다.

 

이후, while문을 통해 n이 0보다 큰 경우네 while문을 돌렸다.

n!=0인 이유는 패키지가격이 기타줄 낱개로 n개를 사는것 보다 싼 경우가 있을 수 있기 때문이다. (기타줄은 쓰고 남아도 되니까)

 

while문 안에 6개 패키지를 사는 것이 싼지, n개를 낱개로 사는 것이 싼지 비교하면서 값을 더해갔다.

하지만, 50퍼센트정도에서 오답이 떴고 패키지 최소 가격보다 낱개 6개 가격이 더 싼 경우가 있지 않을까 싶어서

package가 낱개 X 6 인 경우보다 비쌀 경우, 낱개 X 6의 가격을 저장하고 while문을 돌렸다.

 

결과는 정답이었다.

역시 상식선에서는 접근하면 안되나보다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private final static int STRING_PACKAGE = 6, ONE_STRING = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int packageCost = Integer.MAX_VALUE;
        int stringCost = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            packageCost = Math.min(packageCost, Integer.parseInt(st.nextToken()));
            stringCost = Math.min(stringCost, Integer.parseInt(st.nextToken()));
        }
        br.close();
        solution(n, packageCost, stringCost);
    }

    private static void solution(int n, int packageCost, int stringCost) {
        int answer =0;
        packageCost = Math.min(packageCost, stringCost*STRING_PACKAGE);
        while(n>0) {
            if(packageCost < stringCost*n) {
                answer += packageCost;
                n -= STRING_PACKAGE;
            } else {
                answer += stringCost*n;
                n = 0;
            }
        }
        System.out.println(answer);
    }
}