(Java) 백준 1049번 - 기타줄

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

문제

> Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 
> 따라서 새로운 줄을 사거나 교체해야 한다. 
> 강토는 되도록이면 돈을 적게 쓰려고 한다. 
> 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

> 끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 
각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격,
낱개로 살 때의 가격이 주어질 때,
> 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

접근

필요한 기타줄에 대해 6개 이상이면 낱개 가격들 x 6한거랑 세트들의 가격을 전부 비교하여 젤 작은 가격을 고른다. 그리고 6개보다 작아질 때 까지 위 과정을 반복하다가 6개 미만이면 해당 개수를 낱개개격에 곱한 다음 세트랑 비교하고 가장 작은걸 골라 최종 누적된 가격을 출력한다.

문제해결

> num배열을 크기 Mx2사이즈로 만들고 가격을 세트 낱개 세트 낱개..순서로 저장한다.
> 필요한 줄 N을 6개씩 줄여나갈 것이므로 0보다 클 때까지만 반복해준다.
> 가격은 최대 1000이므로 최대값을 1001로 준 뒤 가장 싼 값을 찾는다.
> n은 그리디를 반복하며 남은 필요한 줄의 수이다.
> N이 6보다 크면 낱개에 6을 곱해주고 비교해 젤 싼걸 찾아주고,
> N이 6보다 작으면 남은 개수를 곱하고 비교해 젤 싼걸 rst에 저장한다.

코드

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main {
    //1049번 기타줄
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int N, M;
    static int[] num;
    static int rst = 0;
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        num = new int[M*2];

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            num[i * 2] = Integer.parseInt(st.nextToken());
            num[i * 2 + 1] = Integer.parseInt(st.nextToken());
        }

        while(N > 0) {
            int Min = 1001;
            int n = N;
            if(N >= 6) n = 6;
            for (int i = 0; i < num.length; i++) {
                if (i % 2 != 0) Min = Math.min(Min, num[i] * n);
                else Min = Math.min(Min, num[i]);
            }
            rst += Min;
            N -= n;
        }
        System.out.print(rst);
    }
}

후기

단순하지만 약간 날카로운 문제였다.