완전범죄

1차 실행 오류
B 도둑이 훔칠 수 있는 물건 중, B의 흔적이 같고, A의 흔적이 다를 때
A 도둑의 최소 흔적을 고르는 경우의 수를 고려하지 않음.

class Solution {
    public int solution(int[][] info, int n, int m) {
        int answer = 0;
        int total = info.length; // 훔칠 물건의 총 개수
        int count = 0; // 훔친 물건의 개수
        int countA = 0; // A 도둑의 흔적 개수
        int countB = 0; // B 도둑의 흔적 개수
        
        for (int i = 0; i < info.length; i++) { 
            if (countB + info[i][1] >= m) { // B 도둑이 훔치지 못할 때
                countA += info[i][0];
                count++;
                if (countA >= n) { 
                    return -1;
                }
            }
            else {
                countB += info[i][1];
                count++;
            }
        }
        if (total > count) { 
            return -1;
        }
        return countA;
    }
}

2차 실행 오류
A 도둑의 흔적이 조금 작더라도 B의 흔적이 훨씬 작은 경우를 고려하지 않음.
ex) (n=100, m=4)
물건 1: A: 10, B: 3
물건 2: A: 9, B: 1
물건 3: A: 9, B: 2

class Solution {
    public int solution(int[][] info, int n, int m) {
        int answer = 0;
        int total = info.length; // 훔칠 물건의 총 개수
        int count = 0; // 훔친 물건의 개수
        int countA = 0; // A 도둑의 흔적 개수
        int countB = 0; // B 도둑의 흔적 개수
        
        // A 도둑의 흔적 개수 내림차순 정렬
        for (int i = 0; i < info.length; i++) {
            for (int j = i + 1; j < info.length; j++) { 
                if (info[i][0] < info[j][0]) { 
                    int temp[] = info[i];
                    info[i] = info[j];
                    info[j] = temp;
                }
            }
        }
        
        // A 도둑의 흔적 내림차순 정렬하며, B 도둑의 흔적 오름차순 정렬
        for (int i = 0; i < info.length; i++) {
            for (int j = i + 1; j < info.length; j++) { 
                    if (info[i][1] > info[j][1]) {
                        if (info[i][0] == info[j][0]) { 
                            int temp[] = info[i];
                            info[i] = info[j];
                            info[j] = temp;
                    }
                }
            }
        }
        
        for (int i = 0; i < info.length; i++) { 
            if (countB + info[i][1] >= m) { // B 도둑이 훔치지 못할 때
                countA += info[i][0]; // A 도둑이 훔침
                count++;
                if (countA >= n) { // A, B 도둑 모두 훔치지 못할 때
                    return -1;
                }
            }
            else {
                countB += info[i][1];
                count++;
            }
        }
        return countA;
    }
}

3차 실행 오류
위와 같은 이유로 4개의 경우의 수가 주어졌을 때 2번째와 4번째를 고르는 것이 정답이 되는 상황이 고려되지 않음

import java.util.Vector;

class Solution {
    public int solution(int[][] info, int n, int m) {
        int answer = 0;
        int total = info.length; // 훔칠 물건의 총 개수
        int countA = 0; // A 도둑의 흔적 개수
        int countB = 0; // B 도둑의 흔적 개수
        Vector<Integer> v = new Vector<Integer>();
        boolean success = true;
        
        for (int i = 0; i < info.length; i++) {
            for (int j = i + 1; j < info.length; j++) { 
                if (info[i][0] < info[j][0]) { 
                    int temp[] = info[i];
                    info[i] = info[j];
                    info[j] = temp;
                }
            }
        }
        // A 도둑의 흔적 내림차순 정렬하며, B 도둑의 흔적 오름차순 정렬
        for (int i = 0; i < info.length; i++) {
            for (int j = i + 1; j < info.length; j++) { 
                    if (info[i][1] > info[j][1]) {
                        if (info[i][0] == info[j][0]) { 
                            int temp[] = info[i];
                            info[i] = info[j];
                            info[j] = temp;
                    }
                }
            }
        }
        for (int i = 0; i < total; i++) {
            int count = 0;
            int index = i;
            while (true) {
                if (countB + info[index][1] >= m) { // B 도둑이 훔쳤을 경우 흔적이 누적 최솟값보다 클 때 
                    countA += info[index][0]; // A 도둑이 훔침
                    count++;
                    if (countA >= n) { // A 도둑이 훔쳤을 때 흔적이 누적 최솟값보다 클 때
                        v.add(-1); // 아무도 훔치지 못하므로 -1 저장
                        success = false;
                        break;
                    }
                }
                else {
                    countB += info[index][1]; // B 도둑이 훔침
                    count++;
                }
                if (count == total) {
                    break;
                }
                index++;
                index %= total;
            }
            if (success) {
                v.add(countA); // A 도둑의 흔적 저장
            }
            success = true;
            countA = 0;
            countB = 0;
        }
        // A 도둑의 흔적 중 가장 적은 흔적 탐색
        answer = 121;
        for (int i = 0; i < v.size(); i++) {
            if (v.get(i) != -1 && v.get(i) < answer) { 
                answer = v.get(i);
            }
        }
        if (answer == 121) {
            return -1;
        }
        return answer;
    }
}

수학적인 사고방식이 너무 어렵다.
더 많은 학습이 필요할 듯 하다.

소요 시간: 1시간 48분

class Solution {
    public int solution(int[][] info, int n, int m) {
        int total = info.length;
        int countA = 0;
        int countB = 0;

        // 정렬 루프
        for (int i = 0; i < total; i++) {
            for (int j = i + 1; j < total; j++) {
                double efficiencyI = (double)info[i][0] / info[i][1];
                double efficiencyJ = (double)info[j][0] / info[j][1];
                if (efficiencyI < efficiencyJ) {
                    int[] temp = info[i];
                    info[i] = info[j];
                    info[j] = temp;
                }
            }
        }

        // 물건 배분 루프
        for (int i = 0; i < total; i++) {
            if (countB + info[i][1] < m) { // B가 가져갈 수 있으면
                countB += info[i][1];
            } else { // 못 가져가면 A가 가져감
                countA += info[i][0];
            }
        }

        return (countA < n) ? countA : -1;
    }
}