알고리즘(징검 다리, 카드 게임)

[징검 다리]

 

* 조건

1. 출발지점(0)부터 도착지(distance)가 존재한다
2. 그 사이에는 바위들의 위치(rocks[])가 주어진다
3. 제거할 수 있는 바위의 수(n)이 주어진다
4. 주어진 바위들 중 n개만큼 제거했을 때 나올 수 있는 거리의 최솟값 중에서 가장 큰 값을 출력한다

 

 

* 알고리즘

• 이분 탐색

 

 

* 로직

• 주어진 바위들을 오름차순 정렬을 한다
• 이분 탐색을 사용할 때, mid 값을 거리의 최솟값으로 생각한다
• 처음엔 현재 돌의 위치 - 출발 위치(base = 0)가 mid보다 작은지를 판별한다
  • 만약 mid 보다 작다면 -> 현재 mid보다 더 낮은 거리가 존재하기 때문에 돌을 제거한다(cnt++)
  • 만약 mid 이상이면 -> base를 현재 돌의 위치로 갱신한다
• 돌을 제거한 개수가 n보다 크다면 => rear = mid-1
• n보다 작거나 같다면 => front = mid + 1

 

import java.util.Arrays;

public class Problem_SteppingLeg {
    public static void main(String[] args) {
        int distance = 25;
        int[] rocks = {2, 14, 11, 21, 17};
        int n = 2;  //제거 가능한 바위 개수

        int answer = solution(distance, rocks, n);
        System.out.println(answer);
    }

    public static int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        Arrays.sort(rocks);

        int front = 1;
        int rear = distance;
        while (front <= rear){
            int mid = (front + rear) / 2;
            
            //최소거리보다 작은 범위를 만드는 돌은 제거
            int removeCnt=0;
            int base = 0;   //0부터 시작
            for(int i=0; i<=rocks.length; ++i){
                int rock;
                if(i == rocks.length) rock = distance;
                else rock = rocks[i];

                if(rock - base < mid) removeCnt++;
                else base = rock;
            }
            
            if(removeCnt > n) rear = mid - 1;
            else {
                answer = mid;
                front = mid+1;
            }
        }

        return answer;
    }
}

 

이전에 풀었던 [예산] 문제처럼 기준이 되는 요소를 찾고 그 기준 값을 이분 탐색으로 해결하려는 접근이 도움이 되었던거 같다.

https://uyoo-story.tistory.com/24

알고리즘(단어 변환, 예산)

 

 

[카드 게임]

 

* 조건

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다
2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다
3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다
4. 왼쪽 더미의 카드(left[])와 오른쪽 더미의 카드(right[])가 주어진다
5. 최종적으로 얻을 수 있는 값 중 최댓값을 출력한다

 

 

* 알고리즘

• DP

 

 

* 로직

• 카드의 수가 남아있다고 했을 때, 기본적으로 3가지 경우의 수가 존재한다
  1. 양쪽 다 버리는 경우 (dp[left+1][right+1])
  2. 왼쪽 카드만 버리는 경우 (dp[left+1][right])
  3. 왼쪽 상단 카드 값 > 오른쪽 상단 카드 값이라면 오른쪽 카드만 버리고 값을 누적하는 경우
     (dp[left][right] + rightCards[right])
• 이렇게 3가지 경우가 한 사이클이 된다고 생각하면 된다
• dp[left][right]: 왼쪽 상단이 left번째고, 오른쪽 상단이 right번째인 상황에서 얻을 수 있는 최댓값
• 1번과 2번의 과정을 하게 되면 두 과정 중에서 최댓값을 일단 dp에 넣는다
• 이후 3번 조건에 부합하게 되면 기존에 갖고 있던 dp 값과 3번의 값 중 최댓값을 갱신한다
• 메모이제이션을 통해 중복을 막고, 이를 반복한다

 

public class Problem_CardGame {
    static int[][] dp;
    static int size;
    static int[] leftCards;
    static int[] rightCards;

    public static void main(String[] args) {
        int[] left = {3, 2, 5};
        int[] right = {2, 4, 1};
        int answer = solution(left, right);

        System.out.println(answer);
    }

    public static int solution(int[] left, int[] right) {
        int answer = 0;
        leftCards = left.clone();
        rightCards = right.clone();
        dp = new int[left.length+1][right.length+1];
        size = left.length;

        answer = doProcess(0, 0);
        return answer;
    }

    private static int doProcess(int left, int right) {
        if(left == size || right == size) return 0;
        if(dp[left][right] > 0) return dp[left][right];

        /*
        * 각각 맨 위에 있는 카드를 기준으로 3가지 경우의 수가 존재한다
        * 1. 양쪽 다 버린 경우
        * 2. 왼쪽만 버린 경우
        * 3. 왼쪽 카드 값 > 오른쪽 카드 값인 상태에서는 오른쪽을 버리고 값을 누적하는 경우
        * */

        //1번과 2번의 경우는 제약 없이 모두 비교해봐야 한다
        dp[left][right] = Math.max(doProcess(left+1, right+1), doProcess(left+1, right));

        //3번 경우의 수
        if(leftCards[left] > rightCards[right]){
            dp[left][right] = Math.max(dp[left][right], doProcess(left, right+1) + rightCards[right]);
        }

        return dp[left][right];
    }
}

 

 

DP 문제를 풀 때 그동안 점화식을 세운뒤 반복문으로 해결하려는 습관이 존재했다. 오늘 같이 문제를 풀었던 형과 의견을 나눠봤는데 DP이면서 한 사이클에서 해결해야하는 경우의 수가 3개 이상이라면 재귀 함수로 해당 함수에서 진행되는 로직을 명확하게 해놓고 메모이제이션을 활용하는게 나름대로 더 명확하다는 것을 느꼈다.