[백준 Java] 24954번 물약 구매

💡문제

[Silver I] 물약 구매 - 24954>

문제 링크

성능 요약

메모리: 294016 KB, 시간: 708 ms

---

🤔접근법

주어진 몰약을 모두 구매할 때 구매하는 순서를 고려하여 물약을 가장 싸게 샀을때 그 비용을 출력하는 문제

범위 체크 및 시간복잡도 예상

• 2 ≤ N < 10
• 1 ≤ 물약의 가격 ≤ 1,000
• 1 ≤ 물약의 할인 가격 ≤ 1,000

풀이법

⭕ 접근 방법. 백트래킹
1. 구매한 물약을 i, 할인 받을 물약을 j 로 하는 2차원 배열 sale[i][j] 를 만들어 할인받을 금액을 담늗다.
2. 재귀함수를 이용하여 depth 번째에 구매할 물약을 선택한다.

• 1 ~ N 물약을 탐색하며 이전에 이미 구매했는지 확인 → 구매 했다면 구매할 수 없다. 다음 물약을 확인
• 구매할 물약을 선택했다면 그 물약을 구매 했을 시 할인되는 물약들의 가격을 갱신
• 재귀함수를 호출하여 depth+1번에 구매할 물약을 선택
• 재귀 빠져 나온 후 구매하지 않은 상태로 돌려야 하기 때문에 가격은 구매하기 전 가격을 돌려놓고 방문처리도 해제한다

3. 모든 물약을 한번씩 다 구매했다면 최소 비용과 비교하여 갱신한다.

➡️ 해당 풀이법의 시간 복잡도 : $O(N! * N * N)$

---

😎SUCCESS

고냥 단박에 성공

---

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_24954 {
    static int N; // 물약의 종류 수
    static int price[]; // 각 물약의 가격
    static int sale[][]; // 각 물약을 구매할 때 할인되는 정보
    static int minCost = Integer.MAX_VALUE; // 물약을 가장 싸게 살 때 필요한 최소 비용
    static boolean visited[]; // 물약을 방문했는지 여부를 저장하는 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine()); // 물약의 종류 수 입력
        price = new int[N+1]; // 물약의 가격을 저장할 배열 초기화
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N+1; i++) {
            price[i] = Integer.parseInt(st.nextToken()); // 각 물약의 가격 입력
        }

        sale = new int[N+1][N+1]; // 물약 할인 정보를 저장할 배열 초기화
        for (int i = 1; i < N+1; i++) {
            int p = Integer.parseInt(br.readLine()); // 물약 할인 정보의 개수 입력
            for (int j = 0; j < p; j++) {
                st = new StringTokenizer(br.readLine());
                int saleIdx = Integer.parseInt(st.nextToken());
                int salePrice = Integer.parseInt(st.nextToken());
                sale[i][saleIdx] = salePrice; // 물약을 구매하면 할인되는 정보 입력
            }
        }

        visited = new boolean[N+1]; // 방문 여부를 저장하는 배열 초기화
        findMinCost(0, 0); // 가장 싸게 물약을 살 때 필요한 최소 비용을 찾는 메서드 호출
        System.out.println(minCost); // 최소 비용 출력
    }

    // 물약을 가장 싸게 살 때 필요한 최소 비용을 찾는 메서드
    private static void findMinCost(int depth, int cost) {
        if(cost >= minCost) return; // 현재 비용이 최소 비용을 초과하면 종료
        if(depth == N){ // 모든 물약을 구매한 경우
            minCost = Math.min(minCost, cost); // 현재 비용과 최소 비용을 비교하여 더 작은 값을 최소 비용으로 갱신
            return;
        }

        for (int i = 1; i < N+1; i++) { // 모든 물약에 대해 반복
            if(visited[i]) continue; // 이미 방문한 물약이면 다음 물약으로 넘어감
            visited[i] = true; // 현재 물약을 방문했음을 표시
            int originPrice[] = Arrays.copyOf(price, N+1); // 물약을 구매하기 전의 가격을 저장
            for (int j = 1; j < N+1; j++) { // 해당 물약을 구매하고 나서 할인되는 물약들에 대해 반복
                if(price[j] - sale[i][j] <=0 ){ // 할인되는 가격이 물약의 가격보다 크면
                    price[j] = 1; // 가격을 1로 설정 (가격은 0 이하는 되지 않음)
                } else { // 그렇지 않으면
                    price[j] -= sale[i][j]; // 할인된 가격으로 업데이트
                }
            }
            findMinCost(depth+1, cost+price[i]); // 다음 물약을 선택하고 재귀적으로 호출
            price = Arrays.copyOf(originPrice, N+1); // 물약을 구매하기 전의 가격으로 되돌림
            visited[i] = false; // 현재 물약 방문 표시 해제
        }
    }
}