📙 Algorithm Solving/Java
📙[Algo] 24.07.16 알고리즘
혜덕hyeduck
2024. 7. 17. 01:13
알고리즘 문제) BOJ 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까지 선택한 경우 성격차의 최솟값
- 여기서 남학우 중에는 커플이 되는 경우, 안 되는 경우 2가지가 존재하므로 아래 2가지 경우가 생긴다.
- 기저조건 : 최대한 많은 커플이 만들어지기 위해서 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. 카드 게임
문제 요약
- 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);
}
}