[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1049번, 기타줄

문제 링크

1049번: 기타줄

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. N개의 기타줄이 망가졌으며, M개의 기타줄 브랜드가 존재합니다.

2. 기타줄을 살 때에는 6개 패키지, 1개의 낱개로 구매할 수 있습니다.

3. N개를 사기 위해 필요한 돈의 최소값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 패키지 및 낱개의 최소값을 이용하여 N개의 기타줄을 구입합니다.

 

3. 기타줄을 구입할 때 가격을 결과로 출력합니다. 

 

 

기타줄 구입.

 

낱개로 살 때 최소값, 패키지로 살 때 최소값을 구합니다.

 

"낱개 최소값 × 6  ≤ 패키지 최소값" 일 때

N개를 낱개 최소값으로 모두 산다.

 

"낱개 최소값 × 6 > 패키지 최소값" 일 때

 

패키지를 구매할 수 있는 만큼 구매합니다.

(N ÷ 6) × 패키지 최소값

 

남은 기타줄을 패키지로 살지, 낱개로 살지 결정합니다.

 

"(N % 6) × 낱개 최소값 ≤ 패키지 최소값" 일 때

남은 기타줄을 모두 낱개로 삽니다.

(N % 6) × 낱개 최소값

 

"(N % 6) × 낱개 최소값 ＜ 패키지 최소값" 일 때

남은 기타줄을 패키지 1개를 구매해서 삽니다.

패키지 최소값

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N : 10

M : 3

 

기타줄 브랜드

	패키지 가격	낱개 가격
브랜드 1	20	8
브랜드 2	40	7
브랜드 3	60	4

 

2. 패키지 및 낱개의 최소값을 이용하여 N개의 기타줄을 구입합니다.

 

패키지 및 낱개 최소값 구하기!

 

패키지 최소값 : 20(브랜드 1)

낱개 최소값 : 4(브랜드 3)

 

기타줄 구입!

 

"낱개 최소값 × 6 > 패키지 최소값"

= "24 > 20"을 만족!

 

패키지 구매 가능할 때까지 풀매수!

 

(N ÷ 6 ) × 패키지 최소값 = (10 ÷ 6) × 20 = 1 × 20 = 20

 

남은 기타줄

N % 6 = 20 % 6 = 4개

 

4개를 패키지로 구매할 지, 낱개로 구매할 지 비교

"(N % 6) × 낱개 최소값 ＜패키지 최소값"

= "16 < 20" 만족

 

남은 기타줄 낱개로 구매

(N % 6) × 낱개 최소값 = (10 % 6) × 4 = 4 × 4 = 16

 

 

3. 기타줄을 구입할 때 가격을 결과로 출력합니다. 

 

패키지 구매 : 20

낱개 구매 : 16

 

36(20 + 16)을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 사용하여 기타줄에 대한 정보를 띄어쓰기 기준 나누었습니다.
• Math.min으로 기타줄의 낱개와 패키지의 최소값을 구합니다.
• 조건들을 비교하면서 기타줄을 낱개 및 패키지로 구매를 진행합니다.
• 기타줄을 구매한 금액의 합을 결과로 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main {
    static int N,M, pack = Integer.MAX_VALUE, piece = Integer.MAX_VALUE, answer;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        //기타줄 브랜드 정보 저장
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine()," ");
            //패키지 및 낱개 최소값 구하기
            pack = Math.min(pack, Integer.parseInt(st.nextToken()));
            piece = Math.min(piece, Integer.parseInt(st.nextToken()));
        }
        //낱개를 6개 살 때 패키지보다 싼지 확인
        if(piece * 6 <= pack)	//"낱개 최소값 × 6  ≤ 패키지 최소값" 확인
            answer = piece * N;	//기타줄 모두 낱개로 구매
        else{
            answer = (N/6) * pack;	//패키지 구매할 수 있을 때까지 구매
            if(N%6 * piece <= pack)	//남은 기타줄 패키지로 구매할지, 낱개로 구매할지 확인
                answer += (N%6) * piece;	//남은 기타줄 낱개로 구매
            else
                answer += pack;	//남은 기타줄 패키지로 구매
        }
        bw.write(answer + "");	//기타줄 구매한 금액 BufferedWriter저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}