[Java] Boj 1049: 기타줄

문제

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

 

풀이

 맨 첫 줄에 구매해야 하는 기타줄의 수와 브랜드 수가 입력된다. 이후 6줄 묶음의 가격과 1줄의 개별 가격이 입력으로 주어지게 된다. 그리디 알고리즘을 이용해야 하는 문제로, 이 문제를 처음 봤을때는 무조건 같은 브랜드에서만 모든 줄을 구매해야 하는 줄 알고 건드리지 못하고 있었는데, 지금와서 잘 읽어보니 두 브랜드에서 섞어서 사도 상관이 없는 문제였다. 문제 해결의 아이디어는 다음과 같다.

 

1) 입력되는 여러 브랜드 중, 가장 싼 6줄 묶음 가격과 가장 싼 개별 1줄의 가격을 구한다.

2) 1)에서 구한 가장 싼 6줄 묶음 / 개별 1줄 가격에 그리디 알고리즘을 적용해 n개의 기타 줄을 구매한다. 

 

 그리 어렵지 않게 구현할 수 있는 문제이다. 가장 싼 6줄 묶음의 가격을 m_x, 가장 싼 개별 1줄의 가격을 m_y에 저장한다. 이때 고려해야 할 사항이 있는데, 개별 1줄을 6개 구매하는게 6줄 묶음으로 사는 것 보다 가격이 싸다면 그냥 개별 1줄로 몽땅 구매하면 된다. 즉, m_y * 6이 m_x보다 작으면 그냥 한 줄로 몽땅 구매하면 된다는 것이다. 이것을 검사한 뒤에는 그냥 그리디 알고리즘을 적용해 6줄 묶음으로 구매하고, 6줄 묶음으로 구매하고 남은 줄이 있을 것이다. 이 남은 줄을 마저 구매할 때, 6줄 묶음으로 사는게 나은지, 1줄씩 개별 구매하는게 더 싼지 검사하고 더 싸게 구매할 수 있는 방식으로 구매하면 된다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int m_x = 1001;
        int m_y = 1001;
        for (int i = 0; i< m; i++) {
            st = new StringTokenizer(bf.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            m_x = Math.min(x, m_x);
            m_y = Math.min(y, m_y);
        }
        int res = 0;
        if (m_x == 0 || m_y == 0) {
            System.out.println(0);
            return;
        }
 
        if (m_y * 6 <= m_x) {
            res = m_y * n;
            System.out.println(res);
            return;
        }
 
        while (n >= 0) {
            if (n >= 6) {
                res += m_x;
                n -= 6;
            }
            if (n < 6) {
                break;
            }
        }
        int use_x = m_x;
        int use_y = m_y * n;
        System.out.println(res + Math.min(use_x, use_y));
 
    }
}
 

 

 코드 중간에 m_x와 m_y가 0인지 검사하는 부분이 있는데, 입력받는 가격에 0이 있을 수 있다고 하여 해당 부분을 추가해 주었다. 그런데 사실 입력받는 가격이 0이면 최솟값으로 저장되므로 저 부분이 없어도 정상적으로 코드는 작성한다...