📙 Algorithm Solving/Java
📙[Algo] 24.05.28 알고리즘
혜덕hyeduck
2024. 5. 29. 02:08
알고리즘 문제) BOJ 5945. Treasure Chest
문제 요약
- N개의 금화가 일렬로 배치되어있고
- 각 금화는 Ci라는 가치를 가지고 있음
- 이때, Bessie와 Bonnie가 번갈아서 라인의 왼쪽 끝이나 오른쪽 끝에서 한 개의 금화를 가져가며, 금화가 없으면 게임이 끝
- 각각 최대한 부를 많이 얻고자 할 때, Bessie가 얻을 수 있는 최대 가치는?
- Bessie부터 시작하며, 각각 최적의 전략을 사용한다.
시간 제한
- 1초
입력
- 정수 N
- 1 ≤ N ≤ 5000
- N+1개 줄에 각 금화의 가치가 주어짐 Ci
- 1 ≤ Ci ≤ 5000
출력
- Bessie가 얻을 수 있는 최대 가치
접근법
- start와 end를 매개변수로 넘겨주면서, 만약 맨 앞을 선택하면 start+1, 맨 뒤를 선택하면 end - 1로 넘겼다.
- 이때, start > end가 되는 순간 게임은 끝난다.
- order 매개변수는 차례가 누구인지 나타내며, 0일때가 bessie, 1일떄가 bonnie다
- 만약 order 가 0일 경우, bessie 차례이며
- 결과값 ret에 두 가지 케이스 중 최댓값을 저장한다
- 케이스1 : 맨 앞 보석 선택
- 케이스2 : 맨 뒤 보석 선택
- 결과값 ret에 두 가지 케이스 중 최댓값을 저장한다
- 만약 order가 1일 경우, bonnie 차례이며
- 결과값 ret에 두 가지 케이스 중 최솟을 저장한다
- 케이스1 : 맨 앞 보석 선택
- 케이스2 : 맨 뒤 보석 선택
- 왜 최솟값? 각 플레이어는 최선의 선택을 하게 되는데, 여기서 ret은 결국 bessie가 갖게되는 가치를 의미하므로 bonnie차례에서는 이 가치가 최소가 되는 경우가 bonnie가 최선의 선택을 하게 되는 걸 의미한다…
- 결과값 ret에 두 가지 케이스 중 최솟을 저장한다
코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[] arr;
static int[][][] dp;
static int recur(int order, int start, int end) {
// order 0 -> bessie(a)
// order 1 -> bonnie(b)
if (start > end) return 0;
if (dp[order][start][end] != -1) return dp[order][start][end];
// 각 플레이어는 매 턴에서 최선의 선택을 하게 된다....
int ret;
if (order == 0) {
// A차례
ret = 0;
ret = Math.max(ret, recur(1, start + 1, end) + arr[start]);
ret = Math.max(ret, recur(1, start, end - 1) + arr[end]);
} else {
// B차례
ret = 1 << 30;
ret = Math.min(ret, recur(0, start + 1, end));
ret = Math.min(ret, recur( 0, start, end - 1));
}
dp[order][start][end] = ret;
return ret;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
dp = new int[2][5010][5010];
for (int[][] d1 : dp) {
for (int[] d2 : d1) {
Arrays.fill(d2, -1);
}
}
System.out.println(recur(0, 0, N - 1));
br.close();
}
}
알고리즘 문제) BOJ 15653. 구슬 탈출 4
문제 요약
- N*M 보드에 빨간 구슬과 파란 구슬이 올려져 있음
- 보드에는 구멍이 하나 존재
- 구슬은 상하좌우로 굴릴 수 있으며, 동시에 움직인다.
- 목표는 빨간 구슬을 구멍을 통해 뺴내는 것이다
- 파란 구슬이 먼저 빠지거나, 동시에 빠지면 실패
- 구슬은 동시에 같은 칸에 존재X
- 구슬이 더이상 움직이지 않을때까지 진행
- 보드 상태가 주어질 때, 최소 몇 번만에 빨간 구슬을 빼낼 수 있을까?
시간 제한
- 2초
입력
- N M
- 3 ≤ N,M ≤ 10
- 다음 N개의 줄에 보드 상태 주어짐
- . : 빈칸
- # : 장애물 또는 벽
- O : 구멍
- R : 빨간 구슬 위치
- B : 파란 구슬 위치
- 가장자리는 모두 #
- 구멍, 구슬 개수는 각각 1개
출력
- 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력
- 불가능하면 -1
접근법
- 한칸만 이동하는 게 아니라, 벽이나 장애물 혹은 구멍을 만날때까지 굴러야하며, 만약 다른 구슬이 있다면 그전에 멈춰야함
- ⇒ 이걸 구현하는게 은근 까다로웠다…
- boolean변수를 활용해서 redStop, blueStop 변수로 벽이나 장애물을 만날 때 true값이 되도록하고, 해당 변수가 false일때만 이동.
- 또한, 장애물이나 벽을 만나면, 한칸 이동 전으로 복원 시켰다
- 또한 구멍을 만난 경우에도 strop변수를 true로 해주었다.
- 만약 stop변수가 둘다 true라면 while문을 탈출하게 된다.
- 만약 둘다 이동한 위치가 구멍이 있는 위치라면, 정답이 아니므로 넘겼고, 빨간 공만 구멍인 경우에는 거리변수 dist+1을 반환시켰다.
- 다른 구슬을 만났는지 체크한 방법은 flag 변수를 사용해서, while문 안에서 먼저 멈춘 구슬 번호로 대입했다. (파란색 : 1, 빨간색 : 2)
- while문 밖에서 두 구슬의 좌표 위치가 같다면, 둘 다 부딪힌 상황을 무시하고 구른 것이라 판단
- flag가 1일 경우 파란색이 먼저 해당 좌표에 도착했던 것이므로 빨간 구슬을 한칸 뒤로 이동 시켰꼬, flag가 2인 경우는 반대 상황으로 처리
- 방문체크는 4차원 배열로 빨간 구슬, 파란 구슬 좌표값을 인덱스로 처리했다.
- 즉 해당 두 구슬이 해당 좌표에 존재헀을 떄로 체크!
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static char[][] board;
static boolean[][][][] visited;
static int reR,reC, blR, blC;
static int[] delR = {-1, 1, 0, 0};
static int[] delC = {0, 0, -1, 1};
static int bfs() {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{reR, reC, blR, blC});
visited[reR][reC][blR][blC] = true;
int size, cRedRow, cRedCol, cBlueRow, cBlueCol, mRedRow, mRedCol, mBlueRow, mBlueCol, flag, dist = 0;
boolean blueStop, redStop;
while (!q.isEmpty()) {
size = q.size();
for (int s = 0; s < size; s++) {
cRedRow = q.peek()[0];
cRedCol = q.peek()[1];
cBlueRow = q.peek()[2];
cBlueCol = q.poll()[3];
for (int dir = 0; dir < 4; dir++) {
mRedRow = cRedRow;
mRedCol = cRedCol;
mBlueRow = cBlueRow;
mBlueCol = cBlueCol;
redStop = false;
blueStop = false;
flag = 0;
// 기울이니까,, 장애물이 없을 때까지 굴럴야한다...ㅠㅠ
while (true) {
if (!redStop) {
mRedRow += delR[dir];
mRedCol += delC[dir];
}
if (!blueStop) {
mBlueRow += delR[dir];
mBlueCol += delC[dir];
}
if (redStop && blueStop) break;
// 파란공 또는 빨간공은 벽이나 장애물을 만나면 이동 X
if (board[mBlueRow][mBlueCol] == '#') {
mBlueRow -= delR[dir];
mBlueCol -= delC[dir];
blueStop = true;
if (flag == 0) flag = 1;
}
if (board[mRedRow][mRedCol] == '#') {
mRedRow -= delR[dir];
mRedCol -= delC[dir];
redStop = true;
if (flag == 0) flag = 2;
}
// 구멍을 만나면 일단 멈추기
if (board[mBlueRow][mBlueCol] == 'O') blueStop = true;
if (board[mRedRow][mRedCol] == 'O') redStop = true;
}
// 파란 공이 먼저 구멍에 들어가면 X (또는 동시에)
if (board[mBlueRow][mBlueCol] == 'O') continue;
// 빨간 공이 먼저 구멍에 들어가면 끝
if (board[mRedRow][mRedCol] == 'O') return dist + 1;
if (mRedRow == mBlueRow && mRedCol == mBlueCol){
if (flag == 1) {
mRedRow -= delR[dir];
mRedCol -= delC[dir];
} else if (flag == 2) {
mBlueRow -= delR[dir];
mBlueCol -= delC[dir];
}
}
if (visited[mRedRow][mRedCol][mBlueRow][mBlueCol]) continue;
visited[mRedRow][mRedCol][mBlueRow][mBlueCol] = true;
q.offer(new int[]{mRedRow, mRedCol, mBlueRow, mBlueCol});
}
}
dist++;
}
return -1;
}
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());
board = new char[N][M];
String input;
for (int i = 0; i < N; i++) {
input = br.readLine();
for (int j = 0; j < M; j++) {
board[i][j] = input.charAt(j);
if (board[i][j] == 'R') {
reR = i;
reC = j;
} else if (board[i][j] == 'B') {
blR = i;
blC = j;
}
}
}
visited = new boolean[N][M][N][M];
System.out.println(bfs());
br.close();
}
}
알고리즘 문제) BOJ 13941. Kronican
문제 요약
- N개의 유리잔이 존재
- 각 유리잔에는 물이 들어 있다
- 당신은 모든 물을 마시고 싶지만, K개 이상 유리잔에서 마시고 싶진 ㅏㄶ다.
- 따라서 하나의 유리잔에서 다른 유리잔으로 물을 부어서 마실 수 있다
- 유리잔 i에서 j로 붓는데 드는 노력의 양은 Cij이다
- 이떄, 노력의 합계가 최소가 되도록 유리잔을 부어서 모든 물을 마시는 방법을 찾아라
시간 제한
- 2초
입력
- N K
- 1 ≤ K ≤ N ≤ 20
- N개의 줄에 N개의 정수가 주어진다.
- 0 ≤ Cij ≤ 10
- Cii는 0
출력
- 목표를 달성하기 위해 필요한 최소한의 노력을 출력
접근법
- N == K → 노력없이 N잔을 다 마시면 됨
- N> K
- 만약 N이 5, K가 2
- 3번 부어야 함
- 즉, N-K번
- 3번 부어야 함
- 만약 N이 5, K가 2
- 결과에 영향을 주는 거
- 어떤 잔을 선택했는지
- 잔을 선택한 순서
- 메모리가 35MB밖에 안 되는 점 주의 → dp를 1차원으로 했고, 선택한 상태값을 비트마스킹으로 저장해서 dp배열 index에 대입
- java에서 1비트 카운트 함수 Integer.bitCount 함수 사용 → 만약 선택한 잔이 N-K개라면 탐색 종료 ⇒ return 0
- 부을 잔 from 선택 → 바깥 for문 i
- 물을 받는 잔 to 선택 → 안쪽 for문 j
- 부울 잔을 선택하면 해당 잔은 다음에 또 사용할 수 없으니까 selected에 상태값 저장, 나중에 &연산할 때 0이 아닌 i나 j는 pass
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, K;
static int[][] arr;
static int[] dp;
static int recur(int selected) {
if (Integer.bitCount(selected) == (N - K)) return 0;
if (dp[selected] != -1) return dp[selected];
int ret = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
if ((selected & (1 << i)) != 0) continue; // 이미 선택된 잔은 건너뛰기
for (int j = 0; j < N; j++) {
if (i == j || (selected & (1 << j)) != 0) continue;
ret = Math.min(ret, recur(selected | (1 << i)) + arr[i][j]); // 최소 비용 계산
}
}
dp[selected] = 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());
K = Integer.parseInt(st.nextToken());
arr = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
if (N == K) {
System.out.println(0);
} else {
dp = new int[1 << N];
Arrays.fill(dp, -1);
System.out.println(recur(0));
}
br.close();
}
}