📙[Algo] 24.07.16 알고리즘

알고리즘 문제) BOJ 1727. 커플 만들기

• 링크 : https://www.acmicpc.net/problem/1727

문제 요약

• 여자친구가 없는 남자 n명과 남자친구가 없는 여자 m명
• 각 사람의 성격은 어떤 정수로 표시
• 최대한 많은 커플을 만들고, 각 커플을 이루는 두 사람의 성격의 차이의 합이 최소가 되도록 하자

시간 제한

• 2초

입력

• 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)
• 다음 줄에는 n명의 남자들의 성격
• 그 다음 줄에는 m명의 여자들의 성격
  • 성격은 1,000,000이하의 자연수

출력

• 성격의 차이의 합의 최솟값을 출력

접근법

• 그리디 + dp로 풀어야 한다.
• 최대한의 커플을 만들면서, 커플들의 성격차 합이 최소가 되게 해야함
  • 최대한의 커플을 만든다 == min(남학우 수, 여학우 수)만큼 만들어져야 함
  • 또한, 각 성별의 성격값을 오름차순 정렬 후, 서로 매칭을 하면 최소한의 성격차가 형성된다. ⇒ 그리디적 접근
• 여학우를 기준으로 커플을 만들기 위해, 수가 많은 성별을 무조건 남학우로 가정한다.
• 매겨변수 b는 현재 가리키는 남학우, g는 현재 가리키는 여학우가 되며,
  • 여기서 남학우 중에는 커플이 되는 경우, 안 되는 경우 2가지가 존재하므로 아래 2가지 경우가 생긴다.
    • 현재 남학우b가 여학우g를 선택하는 경우
    • 현재 남학우b가 여학우를 선택하지 않는 경우
  • 이때, 결과값의 최솟값을 dp에 메모이제이션한다.
    • dp[b][g] : 남학우가 b일 때, 여학우를 g까지 선택한 경우 성격차의 최솟값
• 기저조건 : 최대한 많은 커플이 만들어지기 위해서 M명의 g가 모두 선택된 경우이므로 기저조건은 g==M
• 가지치기 : 아직 커플이 M개 만들어지지 않았는데, 이미 남학우 순회가 끝난 경우는 선택되면 안되므로 가장 큰 값을 반환시켜 가지치기

코드

import java.io.*;
import java.util.*;


public class Main {
    static int N, M;
    static int[] boys;
    static int[] girls;
    static int[][] dp;

    static int recur(int b, int g) {
        // b : 현재 가리키는 남학우
        // g : 현재 가리키는 여학우
        // 커플은 무조건 min(N,M)만큼 만들어져야 함 -> 여기서는 남학우가 더 많으므로, 무조건 M개만큼 선택 될 것

        // M명의 여학우가 선택되었다면 -> 최대한 많은 커플을 만든 것
        if (g == M) return 0;
            // M명의 커플이 안 만들어졌는데 남학우 순회가 다 끝난 경우 -> 가지치기
        else if (b == N) return 1 << 30;

        if (dp[b][g] != -1) return dp[b][g];

        int ret = 1 << 30;

        // 현재 가리키는 여학우 선택
        ret = Math.min(ret, recur(b + 1, g + 1) + Math.abs(boys[b] - girls[g]));

        // 현재 가리키는 여학우 선택 X
        ret = Math.min(ret, recur(b + 1, g));

        dp[b][g] = ret;
        return ret;
    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 코드 정리........
        // 항상 남학우가 수가 많게 조정
        if (N >= M) {
            boys = new int[N];
            girls = new int[M];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                boys[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(boys);

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                girls[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(girls);
        } else {
            int temp = N;
            N = M;
            M = temp;

            boys = new int[N];
            girls = new int[M];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                girls[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(girls);

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                boys[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(boys);
        }

        dp = new int[1010][1010];
        for (int[] d : dp) {
            Arrays.fill(d, -1);
        }

        int ans = recur(0, 0);

        System.out.println(ans);
    }
}

 

알고리즘 문제) BOJ 11062. 카드 게임

• 링크 : https://www.acmicpc.net/problem/11062

문제 요약

• N개의 카드가 일렬로 놓여 있고, 각 카드에는 점수가 적혀있음
• 근우부터 시작하여 번갈아 진행되는데 한 턴에는 가장 왼쪽 or 가장 오른쪽에 있는 카드를 가져갈 수 있음
• 카드가 더 이상 남아있지 않을 때까지 턴은 반복
• 게임의 점수는 자신이 가져간 카드에 적힌 수의 합
• 근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다
• 근우가 얻는 점수를 구하는 프로그램을 작성

시간 제한

• 1초

입력

• 첫 줄에는 테스트케이스의 수 T
  • 1 ≤ T ≤ 50
• 각 테스트케이스 마다 첫 줄에는 카드의 개수 N
  • 1 ≤ N ≤ 1,000
• 두 번째 줄에는 N개의 자연수가 공백으로 구분되어 주어짐
  • 수는 1이상 10,000이하

출력

• 각 테스트케이스마다 근우와 명우가 최선의 전략으로 임할 때 근우가 얻게되는 점수를 줄로 구분하여 출력

접근법

• 게임이론 + dp
• 각 턴마다 플레이어는 가장 최선의 선택을 한다.
  • 근우의 점수를 구하므로, 근우를 기준으로 근우가 최선으로 임하게 될 경우 return값은 최댓값이 된다.
  • 그렇기 때문에, 명우 입장에서 최선으로 임하게 될 경우 return값을 최소로 해야 한다.
• 따라서, turn이 0일때(근우 차례)는 결과 값이 최대가 되는 쪽으로, turn이 1일때(명우 차례)는 결과 값이 최소가 되는 쪽으로 선택하게 한다.
• 매 턴마다 카드의 양끝에서만 선택이 가능하므로, 왼쪽 포인터 start와 오른쪽 포인터 end변수를 활용해 선택할 경우 오른쪽(start + 1) 또는 왼쪽(end - 1)으로 이동시켰다.
  • 또한 start > end가 될 경우 모든 카드를 선택한 경우 이므로 게임을 종료(기저조건)
• N이 1000까지 가능하므로, dp배열에 메모이제이션

코드

import java.io.*;
import java.util.*;


public class Main {
    static int N;
    static int[] arr;
    static int[][][] dp;

    static int recur(int start, int end, int turn) {
        if (start > end) return 0;

        if (dp[start][end][turn] != -1) return dp[start][end][turn];

        int ret = 0;
        if (turn == 0) {
            ret = Math.max(recur(start, end - 1, 1) + arr[end],
                    recur(start + 1, end, 1) + arr[start]);
        } else {
            ret = Math.min(recur(start, end - 1, 0) ,
                    recur(start + 1, end, 0));
        }

        dp[start][end][turn] = ret;
        return ret;
    }

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

        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            N = Integer.parseInt(br.readLine());
            arr = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            dp = new int[1010][1010][2];
            for (int[][] d1 : dp) {
                for (int[] d2 : d1) {
                    Arrays.fill(d2, -1);
                }
            }

            int ans = recur(0, N - 1, 0);
            sb.append(ans).append("\n");
        }
        System.out.println(sb);
    }
}