글 읽기 - 왜 틀렸는지 알고 싶습니다. 테케도 다 맞는데 반례가 무엇이 있을까요??

kimensoo 1년 전 0

input으로 들어온 문자열의 길이를 뎁스로 하고 i번째 문자를 가지고 있는 모든 전공책의 경우의 수를 재귀로 돈 후 문자를 완성시켰을 시 쓰인 책의 모든 가격을 더한 후 현재 min값과 비교해서 갱신하는 식으로 코드를 짰습니다.

분명 테케도 다 맞게 나오고 StringBuilder에 각 전공책 당 몇개의 알파벳을 썼는지도 찍어서 출력해봤는데 모든 경우의 수를 돌기도 했습니다.

혹시 제가 간과한 부분이 있을까요? 아니면 반례라도 부탁드립니다 ㅠㅠ

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

class Book {
    int price;
    char[] name;
    Book(int p, char[] n) {
        this.price = p;
        this.name = n;
    }
}

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static char[] ans;
    static int N, min;
    static int[] visited;
    static Book[] bookList;
    static Set<Character>[] sets;

    public static void main(String[] args) throws IOException {
        init();
        solve(0);
        if(min != Integer.MAX_VALUE) {
            System.out.println(min);
        } else {
            System.out.println(-1);
        }
    }

    static void init() throws IOException {
        min = Integer.MAX_VALUE;
        br = new BufferedReader(new InputStreamReader(System.in));
        ans = br.readLine().toCharArray();
        N = Integer.parseInt(br.readLine());
        visited = new int[N];
        bookList = new Book[N];
        sets = new Set[N];

        for(int i = 0; i < N; i++) {
            sets[i] = new HashSet<>();
            st = new StringTokenizer(br.readLine());
            bookList[i] = new Book(stoi(st.nextToken()), st.nextToken().toCharArray());
            for(int j = 0; j < bookList[i].name.length; j++) {
                sets[i].add(bookList[i].name[j]);
            }
        }

    }

    static void solve(int p) {
        if(p == ans.length) {
            int sum = 0;
            for(int i = 0; i < N; i++) {
                if(visited[i] > 0) {
                    sum += bookList[i].price;
                }
            }
            min = Math.min(min, sum);
            return;
        }

        for(int i = 0; i < N; i++) {
            if(sets[i].contains(ans[p])) {
                visited[i]++;
                solve(p+1);
                visited[i]--;
            }
        }
    }

    static int stoi(String s) {return Integer.parseInt(s);}
}

ahajongs 1년 전 4

AAA

10000 BCD

20000 AAC

50000 DDD

정답 : -1

결과 : 20000

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 틀렸는지 알고 싶습니다. 테케도 다 맞는데 반례가 무엇이 있을까요??

kimensoo 1년 전 0

ahajongs 1년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말