👨‍💻 문제

---

✍️ 풀이

전형적인 다이나믹 프로그래밍 문제이다.

        for (int i=1; i<=gameCnt; i++) {
            int[] currentGameWeaponValue = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
            for (int j=0; j<weaponCnt; j++) {
                dpArr[i][j] = getMinValueExcept(dpArr[i - 1], j) + currentGameWeaponValue[j];
            }
        }

이전 회차 i-1 들의 값들 중
같은 무기 j 를 사용한 값들 중 최솟값에
현재 회차 i 의 무기 소모 시간을 더해 dp배열에 집어넣는다.

이를 반복한 후, 마지막 회차에서의 최솟값을 출력하면 끝이다.

---

📄 전체 소스코드

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

public class Main {

    private static int gameCnt;
    private static int weaponCnt;
    private static int[][] dpArr;

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

        st = new StringTokenizer(br.readLine());
        gameCnt = Integer.parseInt(st.nextToken());
        weaponCnt = Integer.parseInt(st.nextToken());

        dpArr = new int[gameCnt + 1][weaponCnt];

        for (int i=1; i<=gameCnt; i++) {
            int[] currentGameWeaponValue = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
            for (int j=0; j<weaponCnt; j++) {
                dpArr[i][j] = getMinValueExcept(dpArr[i - 1], j) + currentGameWeaponValue[j];
            }
        }
        System.out.println(getMinValueExcept(dpArr[gameCnt]));
    }

    private static int getMinValueExcept(int[] arr, int idx) {
        int result = Integer.MAX_VALUE;
        for (int i=0; i<weaponCnt; i++) {
            if (i == idx) {
                continue;
            }
            result = Math.min(arr[i], result);
        }
        return result;
    }

    private static int getMinValueExcept(int[] arr) {
        int result = Integer.MAX_VALUE;
        for (int i=0; i<weaponCnt; i++) {
            result = Math.min(arr[i], result);
        }
        return result;
    }

}

⏲ 시간 단축 방법

    private static int getMinValueExcept(int[] arr, int idx) {
        int result = Integer.MAX_VALUE;
        for (int i=0; i<weaponCnt; i++) {
            if (i == idx) {
                continue;
            }
            result = Math.min(arr[i], result);
        }
        return result;
    }

해당 메소드는 다른 인덱스들의 값들을 선형으로 탐색해 최소값을 추출한다.
선형탐색으로 간단하게 구현했다.

해당 문제에서 무기의 수는 최대 500이므로,
한 회차를 탐색할 때마다 500 * 500이 소요된다.

이처럼 구현하기 간단하지만 느린 선형탐색보다 좀 더 빠른 방법이 있다.

1 2 3 4 5
위 예시에서 본인의 인덱스를 제외한 최소값을 구하면 아래와 같다.
2 1 1 1 1
이처럼 한 회차에서 나올 수 있는 최소값은 2개다.

아무튼 이러한 성질을 이용하여 회차마다 2개의 최소값과 각각의 인덱스를 기억한다면,
좀 더 빠른 구현을 할 수 있다.

이를 구현한다면 우선순위큐를 사용할 수 있을 것으로 보이는데,
또 생각을 해보니, 그렇다면 dp가 아닌 우선순위큐만으로도 충분히 풀 수 있을 것으로 보인다.

---

📄 전체 소스코드 - 우선순위 큐

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

public class Main {

    private static int gameCnt;
    private static int weaponCnt;

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

        st = new StringTokenizer(br.readLine());
        gameCnt = Integer.parseInt(st.nextToken());
        weaponCnt = Integer.parseInt(st.nextToken());

        PriorityQueue<int[]> prevPq = new PriorityQueue<>(((o1, o2) -> o1[0] - o2[0]));
        PriorityQueue<int[]> curPq;

        prevPq.add(new int[] {0, 0});
        prevPq.add(new int[] {0, 1});

        for (int i=0; i<gameCnt; i++) {
            int[] currentGameWeaponValue = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
            int[] minValue = prevPq.poll();
            int[] secondMinValue = prevPq.poll();
            curPq = new PriorityQueue<>(((o1, o2) -> o1[0] - o2[0]));
            for (int j=0; j<weaponCnt; j++) {
                int value = (j != minValue[1] ? minValue[0] : secondMinValue[0]) + currentGameWeaponValue[j];
                curPq.add(new int[] {value, j});
            }
            prevPq = curPq;
        }
        System.out.println(prevPq.poll()[0]);
    }

}