[백준 - 1049번] 기타줄 - Java //Wello Horld//

이번에는 백준알고리즘의 1049번 "기타줄"문제이다. 다 같이 기타리스트 강토를 도와서 기타줄을 가장 저렴하게 살 수 있게 도와줘 보자

문제 자체는 매우 간단하다. 일단, 입력으로 기타리스트 강토씨 기타의 끊어진 기타줄 개수 N과 기타줄을 살 수 있는 브랜드 M이 주어진다. 먼저 각각의 브랜드에서는 기타줄 6개가 같이 들어있는 패키지 가격이있고, 낱개로 살 때의 가격 2가지의 가격이 있고, 끊어진 기타줄 N개를 사기위해 필요한 최소의 돈을 출력해주는 프로그램을 만들어 주면된다.

먼저 패키지 가격을 집어넣을 Int행렬인 pack과, 낱개 가격을 집어넣을 Int행령인 one을 지정하고, 오름차순으로 정렬해준다.

int[] pack = new int[M];
int[] one = new int[M];
for (int i = 0; i < M; i++) {
  st = new StringTokenizer(br.readLine());
  pack[i] = Integer.parseInt(st.nextToken());
  one[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(pack);
Arrays.sort(one);

이후에, N 이 6보다 작을 때랑, 그렇지 않을 때로 나눠서 각각의 케이스마다 가능한 변수를 생각해 그중 최솟값을 구하게 만드는 알고리즘을 작성했다.

성공한 코드는 아래와 같다.

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

public class sample {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] pack = new int[M];
        int[] one = new int[M];
        int ans = 0;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            pack[i] = Integer.parseInt(st.nextToken());
            one[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(pack);
        Arrays.sort(one);
        if (N < 6) {
            ans += Math.min(pack[0], one[0] * N);
        } else {
            int calcHelp = Math.min(pack[0], one[0] * 6);
            ans += calcHelp * (N / 6);
            ans += Math.min(calcHelp, one[0] * (N % 6));
        }
        bw.write(ans + "\n");

        bw.flush();
        br.close();
        bw.close();
    }
}

 

1049번: 기타줄