인프런 커뮤니티 질문&답변

안녕하세요!

저는 강사님과 전체적으로 유사하지만, 오름차순 정렬하는 부분을 다른 로직으로 작성했습니다.

그러나 해당 로직으로는 백준 채점에서 자꾸 99%에서 틀렸습니다가 나오는데 이유를 도저히 모르겠어서 질문 드립니다.

(참고로 강사님이 하신 방식과 비슷하게 문자열을 배열에 보관하고 한번에 정렬하여 인덱스 0번의 문자열을 출력하는 방식으로 수정했더니 통과했습니다.)

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

public class Main {
    static int n, mp, mf, ms, mv, cost, result;
    static int[] pArr;
    static int[] fArr;
    static int[] sArr;
    static int[] vArr;
    static int[] cArr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        pArr = new int[n + 4];
        fArr = new int[n + 4];
        sArr = new int[n + 4];
        vArr = new int[n + 4];
        cArr = new int[n + 4];

        StringTokenizer st = new StringTokenizer(br.readLine());
        mp = Integer.parseInt(st.nextToken());
        mf = Integer.parseInt(st.nextToken());
        ms = Integer.parseInt(st.nextToken());
        mv = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            pArr[i] = Integer.parseInt(st.nextToken());
            fArr[i] = Integer.parseInt(st.nextToken());
            sArr[i] = Integer.parseInt(st.nextToken());
            vArr[i] = Integer.parseInt(st.nextToken());
            cArr[i] = Integer.parseInt(st.nextToken());
        }

        cost = 15000;
        result = -1;
        for (int i = 1; i < (1 << n); i++) {
            solve(i);
        }

        StringBuilder sb = new StringBuilder();
        if (result == -1) {
            sb.append(result).append('\n');
        } else {
            sb.append(cost).append('\n');
            for (int i = 0; i < n; i++) {
                if ((result & (1 << i)) != 0) {
                    sb.append(i + 1).append(' ');
                }
            }
        }
        System.out.println(sb);
    }

    static void solve(int num) {
        int p = 0;
        int f = 0;
        int s = 0;
        int v = 0;
        int c = 0;
        for (int i = 0; i < n; i++) {
            if ((num & (1 << i)) != 0) {
                p += pArr[i];
                f += fArr[i];
                s += sArr[i];
                v += vArr[i];
                c += cArr[i];
            }
        }
        if (p < mp || f < mf || s < ms || v < mv) return;
        if (cost > c) { // 더 적은 비용이면 비용과 result 갱신하기
            cost = c;
            result = num;
        } else if (cost == c) { // 비용이 같으면 더 빠른 result로 갱신하기
            for (int i = 0; i < n; i++) {
                if ((result & (1 << i)) != (num & (1 << i))) { // i번째 인덱스에 비트가 다르면
                    if ((num & (1 << i)) != 0) { // num이 켜져있으면 사전 순으로 더 빠름
                        result = num;
                    }
                    break;
                }
            }
        }
    }
}