[백준, Java] 24954번, 물약 구매, (백트래킹)

문제 링크

24954번: 물약 구매

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. N개의 물약이 존재하며, 각 물약을 살 때마다 다른 물약의 가격을 할인 받을 수 있습니다.

2. 물약의 가격이 0이하가 되면 최소 비용 1코인으로 물약을 구매하게 됩니다.

3. 모든 물약을 구매할 때 최소 비용의 결과를 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 백트래킹을 통해서 모든 물약을 구매할 때 최소 비용일 때를 탐색합니다.

 

3. 탐색을 통해 얻은 최소 비용의 값을 결과로 출력합니다.

 

백트래킹(물약 구매하기)

 

각 물약을 구매하는 순서를 백트래킹을 통해서 탐색을 진행합니다.

 

 

백트래킹을 진행하면서, 진행되는 경우를 살펴보겠습니다.

 

1. 해당 물약을 구매하면, 주어진 다른 물약의 가격을 내립니다.

 

2. 해당 물약을 구매했으므로, 구매 확인을 진행합니다.

 

3. 다음 물약을 구매를 진행합니다.

✭ 구매를 진행할 때 물약이 0이하일 때에는 최소 비용 1코인으로 구매를 진행합니다.

 

4. 그 상황에서 현재 물약을 구매한 상황을 탐색했기 때문에 이전 상황으로 되돌리기 위해서 내린 다른 물약의 가격을 다시 올립니다. 

 

5. 해당 구매를 취소한 것으로 구매 확인도 취소합니다.

 

 

 

또한, 탐색을 진행하면서 현재 최소 비용보다 탐색 중일 때 비용이 커질 경우에는 어차피, 비용이 계속 추가될 것이므로 현재 최소 비용보다 커질 수 없기 때문에 해당 상황에 탐색을 종료합니다.

 

 

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

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

 

N : 4

 

 

물약.

 

10

15

20

25

 

각 물약 할인 대상

 

1번 물약 : {3, 10}, {2, 20}

 

2번 물약 : -

 

3번 물약 : {4, 10}

 

4번 물약 : {1, 10}

 

2. 백트래킹을 통해서 모든 물약을 구매할 때 최소 비용일 때를 탐색합니다.

 

1번 물약 구매.

 

10

15

20

25

 

다른 물약 할인 하기

 

{3, 10}, {2, 20}

 

10

-5

10

25

 

구매 비용 : 10코인

 

2번 물약 구매.

 

10

-5

10

25

 

다른 물약 할인 하기

 

-

 

10

-5

10

25

 

구매 비용 : 10 + 1 = 11 코인

 

3번 물약 구매.

 

10

-5

10

25

 

다른 물약 할인 하기

 

{4, 10}

 

10

-5

10

15

 

구매 비용 : 10 + 1 + 10  = 21코인

 

4번 물약 구매.

 

10

-5

10

15

 

다른 물약 할인 하기

 

{1, 10}

 

0

-5

10

15

 

구매 비용 : 10 + 1 + 10 + 15  = 36코인

 

1 ► 2 ► 3 ► 4 

 

 

이후, 각 물약 구매한 것을 취소하면서, 탐색을 진행하면

 

1 ► 3 ► 2 ► 4 : 36코인

 

1 ► 3 ► 4 ► 2 : 36코인

 

1 ► 4 ► 2  : 3번을 탐색했을 때 36코인 이상이기 때문에 더 탐색을 하지 않습니다. 

 

1 ► 4 ► 3 : 3번을 탐색했을 때 36코인 이상이기 때문에 더 탐색을 하지 않습니다. 

 

2 ► 1 ► 3 ► 4 : 50코인

 

...   

 

 

 

3. 탐색을 통해 얻은 최소 비용의 값을 결과로 출력합니다.

 

 

1 ► 2 ► 3 ► 4  : 36코인

 

 

36 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 물약의 정보를 띄어쓰기 기준 나누었습니다.
• search를 이용하여 모든 물약을 구매하는 최소 비용을 탐색합니다.
• 탐색한 최소 비용을 Bufferedwriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 백트래킹을 통해 물약 구매를 진행합니다.
• search함수는 물약 구매를 진행할 때 최소 비용보다 커지면 해당 탐색을 종료합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;


public class Main {
    //물약 할인 정보 관련 클래스
    static class Discount{
        int idx;	//할인 대상 물약 Index
        int discount;	//물약 할인 가격
        Discount(int idx, int discount){
            this.idx = idx;
            this.discount = discount;
        }
    }
    //물약 정보 배열
    static int[] position;
    static boolean[] visited;	//물약 구매 확인 배열
    static List<Discount>[] discounts;	//물약 할인 대상 배열
    static int result = Integer.MAX_VALUE;
    static int N;
    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));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        position = new int[N+1];
        visited = new boolean[N+1];
        discounts = new List[N+1];

        //물약 정보 저장
        for(int i=1;i<=N;i++){
            position[i] = Integer.parseInt(st.nextToken());
            discounts[i] = new ArrayList<>();
        }

        //물약 할인 정보 저장
        for(int i=1;i<=N;i++){
            int p = Integer.parseInt(br.readLine());
            for(int j=0;j<p;j++){
                st = new StringTokenizer(br.readLine()," ");
                int idx = Integer.parseInt(st.nextToken());
                int discount = Integer.parseInt(st.nextToken());
                discounts[i].add(new Discount(idx, discount));
            }
        }
        //백트래킹으로 최소 비용 구매 순서 탐색 진행
        search(1, 0);

        //최소 비용 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //백트래킹을 통해서 물약 구매를 진행하여 최소 비용을 탐색합니다.
    static void search(int idx, int coin){

        //현재 구매 비용이 최소 비용 이상인 경우
        if(coin >= result){
            return;
        }

        //모든 물약을 구매했을 경우
        if(idx == N + 1){
            result = Math.min(result, coin);
            return;
        }

        //다음 구매할 물약 탐색하기
        for(int i=1; i<=N;i++){

            //이미 구매한 물약인 경우
            if(visited[i]){
                continue;
            }
            //물약 구매 확인 설정
            visited[i] = true;
            //물약 할인 진행
            for(Discount d : discounts[i]){
                position[d.idx] -= d.discount;
            }
            //다음 구매 물약 탐색
            search(idx + 1, coin + (position[i]  <= 0 ? 1 : position[i]));
            //물약 할인 취소
            for(Discount d : discounts[i]){
                position[d.idx] += d.discount;
            }
            //물약 구매 취소
            visited[i] = false;
        }
    }
}