[백준] 알고리즘 분류(그리디 알고리즘,JAVA)11508번, 2+1 세일

문제 링크

11508번: 2+1 세일

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 3개의 물품을 1개의 팩으로 살 때 가장 싼 물건을 무료로 구매가 가능하다.

2. N개의 유제품을 구매할 때 필요한 최소 비용을 결과로 출력합니다.

3. 정답은 Int형 범위 안에 존재합니다.(정답은 2³¹-1보다 작거나 같다.)

 

 

알고리즘 진행 순서.

 

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

 

2. 유제품 가격 정렬한 뒤, 가격이 비싼것순으로 묶어서 구매를 진행합니다.

 

3. 지불한 금액을 결과로 출력합니다.

 

 

유제품 구입

 

N개의 모든 유제품을 구매할 때 무료로 받는 가격이 최대가 되도록 반복해야합니다.

 

가격 기준 정렬한 뒤 비싼 가격순으로 팩을 담게 된다면

 

무료로 받을 수 있는 최상의 선택만 할 수 있습니다.

 

예제입력 2.

 

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

 

N = 6

 

유제품 정보

 

	유제품1	유제품2	유제품3	유제품4	유제품5	유제품6
가격	6	4	5	5	5	5

 

2. 유제품 가격 정렬한 뒤, 가격이 비싼것순으로 묶어서 구매를 진행합니다.

유제품을 오름차순 정렬

※가격정보를 배열에 저장한 뒤 Arrays.sort를 사용하였습니다.

 

	유제품2	유제품3	유제품4	유제품5	유제품6	유제품1
가격	4	5	5	5	5	6

 

가격이 비싼순 구매 진행!

 

	유제품2	유제품3	유제품4	유제품5	유제품6	유제품1
가격	4	5	5	5	5	6

 

(6, 5, 5) 1팩으로 구매!

 

무료로 받은 제품 : 유제품 5

 

구입 가격 : 6 + 5 = 11

 

	유제품2	유제품3	유제품4	유제품5	유제품6	유제품1
가격	4	5	5	5	5	6

 

(4, 5, 5) 1팩으로 구매!

 

무료로 받은 제품 : 유제품 4

 

구입 가격 : 5 + 5 = 10

 

3. 지불한 금액을 결과로 출력합니다.

 

(6, 5, 5) + (4, 5, 5) = 11 + 10 = 21

 

21을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• Arrays.sort을 이용하여 금액 기준 오름차순 정렬하였습니다.
• 비싼 가격순으로 구매를 진행하며 3번째 물품은 무료로 받는 제품입니다.
• 지불한 금액을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main{
    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));
        int N = Integer.parseInt(br.readLine());
        int[] price = new int[N];
        //유제품 가격 정보 저장
        for(int i=0;i<N;i++)
            price[i] = Integer.parseInt(br.readLine());
        Arrays.sort(price);	//유제품 오름차순 정렬
        int answer = 0;
        //비싼 가격의 유제품 순으로 구매
        //3번째는 무료로 받는 제품
        for(int i=N-1, j=1;i>=0;i--, j++){
            if(j%3 != 0)		//금액 지불하는 유제품
                answer += price[i];
        }
        bw.write(answer + "");		//지불한 금액 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}