[BOJ] 16508: 전공책 (JAVA)

문제

https://www.acmicpc.net/problem/16508

 

여담

완전 탐색하면 for 문만 사용할 것이라는 고정관념에 사로잡혀 있었다. 그래서 결국 오늘도 풀이를 참고해서 풀었다..ㅎ 뭐 이렇게 계속 풀다 보면 실력이 늘겠지!

 

완탐은 재귀로도 풀 수 있다는 것을 기억하자!

 

풀이

주어지는 책의 개수가 최대 16개이므로 완전 탐색과 백트래킹을 사용해서 풀이하면 된다.

 

이때, 현재 책을 고르는 경우와 고르지 않는 경우를 나누어서 탐색해야 하며, 자세한 내용은 다음과 같다.

1. 현재 책을 고르는 경우
   • 책에 포함된 알파벳의 배열 값을 1씩 증가하기
     • count[book.name.charAt(i) - 'A']++
   • total에 현재 책의 가격을 더해서 재귀 호출하기
     • dfs(depth + 1, total + book.price)
2. 현재 책을 고르지 않는 경우
   • 책에 포함된 알파벳의 배열 값을 1씩 감소하기 (∵ 책을 고르는 경우에서 1씩 증가했기 때문)
     • count[book.name.charAt(i) - 'A']--
   • total에 현재 책의 가격을 더하지 않고 재귀 호출하기
     • dfs(depth + 1, total)

 

자세한 내용은 아래의 코드를 참고하면 된다.

 

코드

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

public class Main {
    static final int INF = Integer.MAX_VALUE;
    static int N, minPrice = INF;
    static Book[] books;
    static int[] check = new int[26]; // 만들고자 하는 단어
    static int[] count = new int[26]; // 선택한 책에 포함된 단어
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String T = br.readLine();
        for (int i = 0; i < T.length(); i++) { // 찾으려는 단어에 포함된 문자의 수 세기
            check[T.charAt(i) - 'A']++;
        }

        N = Integer.parseInt(br.readLine());
        books = new Book[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int price = Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            books[i] = new Book(price, name);
        }
        dfs(0, 0);
        if (minPrice == INF) System.out.println(-1);
        else System.out.println(minPrice);
    }

    static void dfs(int depth, int total) {
        if (depth == N) { // 모든 책을 탐색한 경우
            // 원하는 단어를 모두 찾았다면 더 작은 값으로 갱신하기
            if (checkWord()) minPrice = Math.min(minPrice, total);
            return;
        }

        Book book = books[depth];
        // 현재 책을 선택하는 경우
        for (int i = 0; i < book.name.length(); i++) {
            count[book.name.charAt(i) - 'A']++; // 책 제목에 포함된 단어 모두 세기
        }
        dfs(depth + 1, total + book.price);

        // 현재 책을 선택하지 않는 경우
        for (int i = 0; i < book.name.length(); i++) {
            count[book.name.charAt(i) - 'A']--; // 책 제목에 포함된 단어 셌던 거 모두 빼기
        }
        dfs(depth + 1, total);
    }

    static boolean checkWord() { // 원하는 단어를 만들 수 있는지 확인
        // 만들고 싶은 단어를 찾았다면 check 값은 count 값보다 작거나 같아야 함
        for (int i = 0; i < check.length; i++) {
            if (check[i] > count[i]) return false;
        }
        return true;
    }

    static class Book {
        int price;
        String name;

        public Book(int price, String name) {
            this.price = price;
            this.name = name;
        }
    }
}

---

참고

https://subin-programming.tistory.com/303