Today's Algorithm(2019-01-22)

programmers. 서울에서 경산까지

이 또한 동적문제인데요. 이 전 문제에서 동적계획문제에 대한 감을 잡았다고 생각했는데 생각보다 쉽지 않더라구요. 이전에도 말씀드렸듯이 동적문제에서는 dp배열을 어떻게 정의하느냐가 가장 중요합니다. 저는 처음에 이렇게 가정했습니다.

dp[i][j] : 도보로 i번째, 자전거로 j번째 이동했을 때 최대 모금액

그럴듯하죠. 이전에도 이런식으로 문제를 풀었으니까요. 그런데 이게 제대로 작동할까요? 아닐 것 같습니다. 이전 카드문제에서는 left, right 배열이 각각 따로 주어져서 '왼쪽에서 i번째, 오른쪽에서 j번째'가 가능했습니다. 하지만 이번의 경우는 조금 다릅니다. 왜냐하면 하나의 일련의 구간에 대해 도보와 자전거 중 하나를 골라서 타야하기 때문이죠. 그리고 시간에 대한 고려도 없습니다.

 

그럼 이건 어떨까요?

dp[i][j] : i번째 도시에서 시간이 j일때 최대 모금액

도보와 자전거에 대한 내용은 dp배열 상에 없지만 계산상에는 들어있습니다. 이와 같이 꼭 도보와 자전거와 같이 대상이 되는 데이터가 dp배열의 정의로 들어가는 것이 아니라 해당 문제의 조건이 정의로 존재할 수 있다는 것이 인상깊었습니다. 이 문제 또한 다른 사람의 코드를 통해 힌트를 얻긴 했지만 소중한 경험이라 생각합니다.

 

이렇게 정의만 끝나면 이제는 계산을 어떻게 하는지가 중요하겠죠. j가 시간이 되기 때문에 조건에 만족하지 않는 시간은 고려할 필요가 없습니다. 그렇기 때문에 visit이라는 dp배열과 같은 크기의 배열을 만들어서 계산된 시간이 있는 칸에 visit표시를 해두어야 합니다. 만약 visit 표시가 있는 곳이 반복문을 돌다가 발견하게 되면 거기에서 또 다시 K 시간을 넘지 않고 최대 모금액을 모을 수 있는 다음 칸을 채워줄 것입니다. 코드를 보겠습니다.

class Solution {
    public int solution(int K, int[][] travel) {
        int answer = 0;

        int n = travel.length;
        int[][] dp = new int[n + 1][K + 1];
        boolean[][] visit = new boolean[n + 1][K + 1];

        visit[0][0] = true;  // 처음은 무조건 계산되도록
        for (int i = 0; i < n; i++) {
            int wt = travel[i][0];
            int wc = travel[i][1];
            int bt = travel[i][2];
            int bc = travel[i][3];

            for (int j = 0; j <= K; j++) {
                if(!visit[i][j]) continue;  // 고려대상이 아닌 시간을 통과
                if(j + wt <= K) {
                    dp[i + 1][j + wt] = dp[i][j] + wc;
                    visit[i + 1][j + wt] = true;
                }
                if(j + bt <= K) {
                    dp[i + 1][j + bt] = Math.max(dp[i + 1][j + bt], dp[i][j] + bc);  // 위 도보로 인한 값이 들어있을 수 있으므로 max이용!
                    visit[i + 1][j + bt] = true;
                }
            }
        }

        for (int i = 0; i <= K; i++) {
            answer = Math.max(answer, dp[n][i]);
        }

        return answer;
    }
}

 

 

programmers. 예산

이분탐색 부류의 문제를 이전에 잘 풀어본 적이 없어서 처음 풀 때 조금 겁이 났습니다. 그래서 어떻게 접근해야할지 몰라 백준에서 이분탐색 문제를 푼 다른 사람의 코드를 봤는데요. 문제 푸는 방식은 분명 이전에 어디선가 배웠던 접근방식인 것 같아요. 대충 설명하면 이런 것이죠.

while(mid + 1 < high) {  // 64, 65와 같이 1차이 날때 무한루프를 막기위해 +1 더해줌
    int mid = (low + high) / 2;
    /* 
    	문제 조건에 맞게 가공 
    	if(특정 조건) high = mid;
    	else low = mid;
    */
}

그러니까 특정 조건을 만족하는 최적의 값을 찾기 위해 high와 low를 움직여가며 범위를 좁혀나가는 것입니다. 그럼 코드를 바로 살펴보도록 하겠습니다.

 

class Solution {
    public int solution(int[] budgets, int M) {
        int length = budgets.length;

        Arrays.sort(budgets);

        int low = budgets[0];
        int high = budgets[length - 1];

        if(low > (M / length)) return M / length;
        while(low + 1 < high) {
            int mid = (low + high) / 2;
            int newBudget = makeNewBudet(budgets, mid);
            if(newBudget >= M) high = mid;
            else low = mid;
        }

        return chooseBestChoice(budgets, M, low, high);
    }

    private int chooseBestChoice(int[] budgets, int M, int low, int high) {
        if(M <= makeNewBudet(budgets, high)) return low;
        return high;
    }

    int makeNewBudet(int[] budgets, int mid) {
        int temp = 0;
        for (int budget : budgets) {
            if(budget > mid) {
                temp += mid;
                continue;
            }
            temp += budget;
        }
        return temp;
    }
}

문제를 풀 때 다음 2가지에 막혔습니다.

• 마지막에 high와 low 중 어떤 것을 선택할 것인가?
• 왜 테스트9번만 틀릴까?

 

먼저 첫번째 의문에서 while문만 반복해서 문제의 답을 찾을 수 있게끔 하고 싶었습니다. 하지만 while문은 범위를 좁힐 뿐 최적의 답을 찾을 수 없다고 생각하였고 그렇기 때문에 chooseBestChoice()를 통해 최적의 답을 찾을 수 있도록 하였습니다. 둘 중 어느 것이 최선인지 모르기 때문에.. 혹시 더 좋은 방법이 있을 수 있겠지만 더 생각이 안나더라구요.

두번째 의문에서 테스트9번이 틀리는 이유는 제가 특정 경우를 생각하지 못해서 인데요. 그 경우는 주어진 예산 중 가장 작은 값이 (M / length)보다 클 때입니다. 그건 while문에서 해결할 수 있는 범위 밖이거든요. 이 경우는 정말 떠오르기 힘들더라구요. 질문 게시판의 도움을 얻었습니다..!!