내일은 알고리즘

https://www.acmicpc.net/problem/1303

어... 정신을 차리니 마지막 PS로부터 3주 가량이 지났습니다.

추석연휴가 껴 있기도 했고, 개인적인 일로 지방을 오가느라 시간이 없기도 했고.... 무엇보다 근무도 바빴고... 여러 사정이 있었지만 결국엔 제가 게을렀던 거겠죠.

Java를 하도 안쓰다 보니 (현재 하고 있는 업무에서 90% 이상 Python을 씁니다.) 다 까먹어가고 있는 느낌이라 급하게 쉬운 문제를 하나 풀어봤습니다.

정말 기본적인 bfs 문제라 딱히 설명할건 없네요. visit 체크만 잘해주면 풀리는 문제였습니다. 주의 할 점은 N과 M이 거꾸로 주어진다는 정도입니다. 예제에서 티가 안나는 부분이라(예제 입력에선 N == M입니다.) 첫 제출에서 index 범위가 넘어가는 런타임 에러를 당했네요. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class q1303_BOJ_전쟁전투 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

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

		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int B = 0;
		int W = 0;

		int[][] map = new int[N][M];
		Queue<int[]> queue = new LinkedList<int[]>();

		for (int n = 0; n < N; n++) {
			char[] line = br.readLine().toCharArray();
			for (int m = 0; m < M; m++) {
				map[n][m] = (line[m] == 'W') ? 0 : 1;
			}
		}

		for (int n = 0; n < N; n++) {
			for (int m = 0; m < M; m++) {
				if (map[n][m] == 0 || map[n][m] == 1) {
					int target = map[n][m];
					int count = 0;
					queue.offer(new int[] { n, m });
					map[n][m] = -1;

					while (!queue.isEmpty()) {
						int[] now = queue.poll();
						count += 1;

						for (int i = 0; i < 4; i++) {
							int nx = now[0] + delta[i][0];
							int ny = now[1] + delta[i][1];

							if (isIn(nx, ny, N, M) && map[nx][ny] == target) {
								queue.offer(new int[] { nx, ny });
								map[nx][ny] = -1;
							}
						}

					}

					if (target == 0) {
						W += (count * count);
					} else {
						B += (count * count);
					}
				}
			}
		}

		sb.append(W).append(" ").append(B);

		System.out.println(sb);
	}

	private static boolean isIn(int x, int y, int n, int m) {
		return 0 <= x && x < n && 0 <= y && y < m;
	}
}

https://www.acmicpc.net/problem/17472

다리만들기 1과는 비슷한듯 전혀 다른 문제입니다.

각 섬들을 다리로 연결하는 부분은 같지만, 다리만들기1 문제와 다르게 다리는 직선으로만 가능하며 모든 섬이 연결되도록 완성해야 하고 이때 다리의 길이가 2이상인 최소한의 다리를 활용해야 합니다.

이 문제는 크게 3가지 과정으로 나눌 수 있습니다.

1. 주어진 지도에서 섬의 영역을 확인하고 이름 붙이기

2. 각각의 섬에서 다른 섬으로 잇는 최단 다리를 모두 만들기

3. 다리를 선택해 모든 섬들이 연결되게 만들기.

1,2번 과정은 다리만들기 1번 문제와 비슷하고 3번 과정은 MST(최소 스패닝 트리)를 구하는 과정으로 만들 수 있습니다.

즉, 각각의 섬들이 노드가 되고 각 섬들에서 다른섬으로 연결되는 최소거리의 다리가 엣지가 되는 식입니다.

MST를 만드는 알고리즘은 여러 종류가 있는데 우선순위 큐와 Union만을 이용해 간단하게 구현할 수 있는 크루스칼(Kruskal) 알고리즘을 사용했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class q17472__BOJ_다리만들기2 {
	static StringTokenizer st;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[] parent;
	static int N, M;

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

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

		int[][] map = new int[N][M];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < M; m++) {
				map[n][m] = Integer.parseInt(st.nextToken()) * -1;
			}
		}

		int island = 1;
		Queue<int[]> queue = new LinkedList<>();

		for (int n = 0; n < N; n++) {
			for (int m = 0; m < M; m++) {
				if (map[n][m] == -1) {
					queue.offer(new int[] { n, m });
					map[n][m] = island;

					while (!queue.isEmpty()) {
						int[] now = queue.poll();
						int x = now[0];
						int y = now[1];

						for (int i = 0; i < 4; i++) {
							int nX = x + delta[i][0];
							int nY = y + delta[i][1];
							if (isIn(nX, nY) && map[nX][nY] == -1) {
								queue.offer(new int[] { nX, nY });
								map[nX][nY] = island;
							}
						}
					}
					island++;
				}
			}
		}

		int[][] graph = new int[island][island];

		for (int is = 1; is <= island; is++) {
			boolean[][] visit = new boolean[N][M];

			for (int n = 0; n < N; n++) {
				for (int m = 0; m < M; m++) {
					if (map[n][m] == is) {
						queue.offer(new int[] { n, m, 0, 5 });
						visit[n][m] = true;
					}
				}
			}

			while (!queue.isEmpty()) {
				int[] now = queue.poll();
				int x = now[0];
				int y = now[1];
				int l = now[2];
				int dir = now[3];

				if (dir == 5) {
					for (int i = 0; i < 4; i++) {
						int nX = x + delta[i][0];
						int nY = y + delta[i][1];
						if (isIn(nX, nY) && !visit[nX][nY] && map[nX][nY] == 0) {
							queue.offer(new int[] { nX, nY, l + 1, i });
							visit[nX][nY] = true;
						}
					}
				}

				else {
					int nX = x + delta[dir][0];
					int nY = y + delta[dir][1];
					if (isIn(nX, nY) && !visit[nX][nY]) {

						if (map[nX][nY] == 0) {
							queue.offer(new int[] { nX, nY, l + 1, dir });
							visit[nX][nY] = true;
						} else {
							if (graph[is][map[nX][nY]] == 0 && 1 < l) {
								graph[is][map[nX][nY]] = l;
							}
							visit[nX][nY] = true;
						}
					}
				}
			}
		}

		int answer = 0;
		parent = new int[island];
		for (int n = 1; n < island; n++) {
			parent[n] = n;
		}
		PriorityQueue<int[]> pqueue = new PriorityQueue<>((e1, e2) -> {
			return e1[0] - e2[0];
		});

		for (int from = 1; from < island; from++) {
			for (int to = 1; to < island; to++) {
				if (graph[from][to] != 0) {
					pqueue.offer(new int[] { graph[from][to], from, to });
				}
			}
		}

		while (!pqueue.isEmpty()) {
			int[] now = pqueue.poll();
			int l = now[0];
			int from = now[1];
			int to = now[2];

			if (find(from) != find(to)) {
				answer += l;
				union(from, to);
			}
		}

		boolean flag = false;
		int parent = find(1);
		for (int n = 1; n < island; n++) {
			if (find(n) != parent) {
				flag = true;
				break;
			}
		}

		if (flag) {
			System.out.println(-1);
		} else {
			System.out.println(answer);
		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < M) {
			return true;
		}
		return false;
	}

	static int find(int i) {
		if (i == parent[i])
			return i;
		return parent[i] = find(parent[i]);
	}

	static void union(int x, int y) {
		x = find(x);
		y = find(y);

		if (x > y)
			parent[x] = y;
		else
			parent[y] = x;
	}
}

https://www.acmicpc.net/problem/2146

구현을 신경써야 하는 문제입니다.

문제를 2개의 과정으로 나눌 수 있습니다.

1. 주어진 지도에서 섬의 영역을 확인하고 이름 붙이기

2. 각각의 섬에서 다른 섬으로 잇는 다리 만들기

1번은 BFS DFS아무것이나 원하는 방법으로 구현하면 됩니다.

2번의 경우는 BFS를 이용하는것이 구현과 이해가 간편합니다.

시간 단축을 위해서는 모든 경우에 대해 다리를 구하고 다리의 길이를 비교하는 것 보다는 최소값을 다리가 완성될 때 마다 갱신하고, 이미 구해진 최솟값을 넘는 경우에는 Queue를 비워버리고 스킵하는 것이 훨씬 빠릅니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class q2146_BOJ_다리만들기 {
	static StringTokenizer st;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] map;
	static int[] parent;
	static int N;

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

		N = Integer.parseInt(br.readLine());

		map = new int[N][N];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < N; m++) {
				map[n][m] = Integer.parseInt(st.nextToken()) * -1;
			}
		}

		int island = 1;

		for (int n = 0; n < N; n++) {
			for (int m = 0; m < N; m++) {
				if (map[n][m] == -1) {
					dfs(n, m, island);
					island++;
				}
			}
		}

		int answer = Integer.MAX_VALUE;
		Queue<int[]> queue = new LinkedList<>();
		for (int is = 1; is <= island; is++) {
			boolean[][] visit = new boolean[N][N];

			for (int n = 0; n < N; n++) {
				for (int m = 0; m < N; m++) {
					if (map[n][m] == is) {
						queue.offer(new int[] { n, m });
						visit[n][m] = true;
					}
				}
			}

			int l = 0;

			while (!queue.isEmpty()) {
				int size = queue.size();

				for (int s = 0; s < size; s++) {

					int[] now = queue.poll();
					int x = now[0];
					int y = now[1];

					for (int i = 0; i < 4; i++) {
						int nX = x + delta[i][0];
						int nY = y + delta[i][1];
						if (isIn(nX, nY) && !visit[nX][nY]) {

							if (map[nX][nY] == 0) {
								queue.offer(new int[] { nX, nY });
								visit[nX][nY] = true;
							} else {
								answer = Math.min(answer, l);
								visit[nX][nY] = true;
							}
						}
					}
				}
				l++;
				if (l > answer) {
					queue.clear();
				}
			}
		}
		System.out.println(answer);

	}

	static void dfs(int x, int y, int name) {
		map[x][y] = name;

		for (int i = 0; i < 4; i++) {
			int nX = x + delta[i][0];
			int nY = y + delta[i][1];
			if (isIn(nX, nY) && map[nX][nY] == -1) {
				dfs(nX, nY, name);
			}
		}

	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < N) {
			return true;
		}
		return false;
	}
}

https://www.acmicpc.net/problem/1562

풀이방법 아이디어를 떠올리기 힘든 비트마스킹을 활용한 DP문제입니다.

계단수라는 것은 각 자리수의 차이가 1입니다.

즉 N-1자리의 마지막 자리가 X로 끝나는 계단수가 있다면 이 뒤에 X와 1 차이가 나는 숫자를 붙여서 N자리의 계단수를 만들 수 있습니다.

1자리의 계단수는 모두 9개로 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]입니다. (0으로 시작하는 수는 계단수가 아님)

2자리의 계단수는 1자리의 계단수에 1차이가 나는 숫자를 붙여서 만들 수 있고 마지막 자리의 숫자에 따라

10 - 0으로 끝남

21 - 1로 끝남

12 32 - 2로 끝남

23 43 - 3으로 끝남

34 54 - 4로 끝남...

이런 식으로 구분됨을 알 수 있습니다.

이때 위에서 얘기했던것처럼 0으로 끝나는 계단수는 이전 N-1자리에서 1로 끝난 계단수에 0을 붙여 만든 것이고 1로 끝나는 계단수는 0으로 끝나거나 2로 끝난 계단수에 1을 붙여 만든 것입니다.

(이번 경우에는 0으로 끝나는 1자리수 계단수가 존재하지 않습니다.)

이 방법을 N번 반복하면 우리는 X로 끝나는 N자릿수의 계단수를 구할 수 있습니다.

다만 문제에서는 0~9까지 10개의 숫자를 모두 사용한 계단수를 묻습니다.

따라서 해당 계단수에 어떤 숫자가 사용되었는지를 기억해야하는데, 개수와 상관없이 사용의 여부만 알면 되기 때문에 비트마스킹을 활용할수 있습니다.

이제 위의 아이디어를 구현하면 됩니다.

다만 N자리 계단수를 구하기 위해 필요한 N-1자리의 계단수를 고려하는것은 너무 복잡하기 때문에 N-1단계에를 완전탐색하며 이 값을 N자리 계단수로 누적합해주는 식으로 코드를 짜는게 더 간단합니다.

그리고 조건으로도 주어졌지만 진행 과정중에 변수의 범위를 넘는 경우를 막기 위해 누적될 때마다 주어진 값으로 mod 연산을 해야합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class q1562_BOJ_계단수 {

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

		int max = (1 << 10);
		int mod = 1_000_000_000;

		int[] bit = new int[10];
		for (int i = 0; i < 10; i++) {
			bit[i] = 1 << i;
		}

		int N = Integer.parseInt(br.readLine());
		int[][][] dp = new int[10][N + 1][max];

		for (int i = 1; i < 10; i++) {
			dp[i][1][bit[i]] = 1;
		}

		for (int n = 1; n < N; n++) {
			for (int j = 1; j < max; j++) {
				dp[1][n + 1][j | bit[1]] = (dp[1][n + 1][j | bit[1]] + dp[0][n][j]) % mod;
				for (int i = 1; i < 9; i++) {
					dp[i - 1][n + 1][j | bit[i - 1]] = (dp[i - 1][n + 1][j | bit[i - 1]] + dp[i][n][j]) % mod;
					dp[i + 1][n + 1][j | bit[i + 1]] = (dp[i + 1][n + 1][j | bit[i + 1]] + dp[i][n][j]) % mod;
				}
				dp[8][n + 1][j | bit[8]] = (dp[8][n + 1][j | bit[8]] + dp[9][n][j]) % mod;
			}
		}

		int sum = 0;

		for (int i = 0; i < 10; i++) {
			sum = (sum + dp[i][N][max-1]) % mod;
		}

		System.out.println(sum);

	}
}

https://www.acmicpc.net/problem/1194

BFS + 비트마스킹으로 풀이하는 문제입니다.

벽부수기 같은 문제처럼 visited 체크를 열쇠의 소유상태에 따라 다르게 해줘야 합니다.

해당 부분을 비트마스킹 Integer로 저장하거나 배열을 통해 저장하거나 편한 방법으로 풀이할 수 있습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class q1194_BOJ_달이차오른다가자 {
	static StringTokenizer st;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int R, C;

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

		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		char[][] map = new char[R][C];
		boolean[][][] visited = new boolean[R][C][64];

		Queue<Player> queue = new LinkedList<>();

		for (int r = 0; r < R; r++) {
			String input = br.readLine();
			for (int c = 0; c < C; c++) {
				map[r][c] = input.charAt(c);
				if (map[r][c] == '0') {
					queue.offer(new Player(r, c, 0));
					visited[r][c][0] = true;
					map[r][c] = '.';
				}
			}
		}

		int time = 0;
		boolean flag = false;

		loop: while (!queue.isEmpty()) {
			int size = queue.size();
			time++;
			while (size-- > 0) {
				Player p = queue.poll();
				int x = p.x;
				int y = p.y;
				int key = p.key;

				for (int i = 0; i < 4; i++) {
					int nX = x + delta[i][0];
					int nY = y + delta[i][1];
					if (isIn(nX, nY) && map[nX][nY] != '#' && !visited[nX][nY][key]) {
						if (map[nX][nY] == '.') {
							queue.offer(new Player(nX, nY, key));
							visited[nX][nY][key] = true;
						} else if (map[nX][nY] == '1') {
							flag = true;
							break loop;
						} else if (map[nX][nY] < 'a' && canOpen(map[nX][nY], key)) {
							queue.offer(new Player(nX, nY, key));
							visited[nX][nY][key] = true;
						} else if (map[nX][nY] >= 'a') {
							int nKey = (1 << (map[nX][nY] - 'a')) | key;
							queue.offer(new Player(nX, nY, nKey));
							visited[nX][nY][nKey] = true;
						}
					}
				}
			}

		}

		if (flag) {
			System.out.println(time);
		} else {
			System.out.println("-1");
		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < R && 0 <= y && y < C) {
			return true;
		}
		return false;
	}

	static boolean canOpen(char door, int key) {
		if ((1 << (door - 'A') & key) > 0) {
			return true;
		}
		return false;
	}

	static class Player {
		int x, y, key;

		public Player(int x, int y, int key) {
			this.x = x;
			this.y = y;
			this.key = key;
		}
	}
}

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

https://www.acmicpc.net/problem/12919

https://nodingco.tistory.com/30 의 시리즈 문제입니다.

1. 이해 (5분) - 1분

A와 B 문제와 언뜻 보면 똑같아보이는 문제입니다. 

하지만 조금 생각해보면 풀이를 위한 접근 방식이 전혀 다른걸 알 수 있습니다. 

앞의 문제에선 연산을 통한 결과가 맨 뒤 알파벳으로 나타나서 역순으로 따라가기만 하면 문제의 풀이가 가능하지만, 해당 문제에선 알파벳을 먼저 붙이고 뒤집기 때문에 맨 뒤 알파벳이 어떤 연산을 통해 나온 것인지 여러 경우가 생깁니다.

대신 문자열의 형태를 보고 어느정도 경우를 좁힐 수 있고 문자열의 길이도 앞 문제보다 훨씬 작습니다.

2. 계획 (5분) - 3분

재귀를 통해 뒷 문자열을 만들기 위해 가능한 경우를 역으로 되짚어갑니다.

대신 두가지 경우를 매 번 탐색하는게 아니라, 맨 뒷 문자가 A거나 맨 앞 문자가 B일때만 탐색합니다.

(1번 연산이 진행되면 문자열의 맨 뒤는 무조건 A, 2번 연산이 진행되면 맨 앞이 무조건 B)

그렇게 줄인 문자열의 길이가 앞의 문자열과 같아지면 두 문자열이 같은지, 즉 문제의 조건이 가능한지를 체크하고 그 결과를 저장합니다. 이때 True False에 따라 재귀문을 끝내는 조건을 움직여서 가능여부가 한 번 찾아지면 덮어씌워지지 않게했습니다.

3. 검증 (5분) - 1분

검증내용은 A와B 1번 문제와 유사하기때문에 패스하겠습니다.

4. 풀이 (30분) - 17분

재귀문 구현 부분은 조금 신경썼지만, 문자열을 조정하는 부분은 오히려 앞 문제보다 쉽게 구현 할 수 있었습니다.

5. 채점, 디버깅 

다행히 이번에도 한 번에 통과했습니다. 감사합니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int N;
	static char[] S;

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

		S = br.readLine().toCharArray();
		char[] T = br.readLine().toCharArray();

		N = S.length;

		makeS(T, T.length);

		if (N == 100) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}

	static void makeS(char[] T, int l) {
		if (l < N) {
			return;
		}
		if (l == N) {
			N = (checkS(T)) ? 100 : N;
			return;
		}

		if (T[l - 1] == 'A') {
			char[] newT = new char[l - 1];
			for (int i = 0; i < l - 1; i++) {
				newT[i] = T[i];
			}
			makeS(newT, l - 1);
		}

		if (T[0] == 'B') {
			char[] newT = new char[l - 1];
			for (int i = 0; i < l - 1; i++) {
				newT[i] = T[l - 1 - i];
			}
			makeS(newT, l - 1);
		}
	}

	static boolean checkS(char[] T) {
		for (int n = 0; n < N; n++) {
			if (T[n] != S[n]) {
				return false;
			}
		}
		return true;
	}
}

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

https://www.acmicpc.net/problem/12904

1. 이해 (5분) - 2분

원리를 깨달으면 간단한 시뮬레이션 문제입니다.

다만, 문자열 관련해서 코드를 작성할 이해도가 필요할 것 같습니다.

문제는 간단명료합니다. 앞의 문자열에 두 가지 연산을 적용해서 뒤 문자열을 만들 수 있는지를 찾습니다.

간단히 생각하면 앞의 문자에 두가지 연산을 계속 적용해서 가능한 모든 경우의 수를 볼 수도 있겠지만... 

S의 길이가 1이고, T의 길이가 1000이라면? 2^1000가지 경우를 탐색해야 하니 어마어마한 일이겠죠. 

대신 연산의 조건을 파악하고 완성된 문자열에서 거꾸로 짚어가는 식으로 가부를 판단하려고 합니다.

2. 계획 (5분) - 4분

문자열에 적용한 연산 두가지는 모두 뒤쪽에 알파벳을 하나 더 붙입니다.

즉 최종결과에서 가장 뒤에 있는 알파벳은 이전에 적용된 연산이 무엇이었는지를 알려줍니다.

두 번째 문자열이 앞의 문자열보다 더 긴 길이만큼 연산을 거꾸로 적용하면 앞의 문자열과 같은 길이의 가능한 문자열이 나오게 되고 이 문자열을 앞의 문자열과 비교해서 가부를 판단할 수 있습니다.

문자열을 실제로 뒤집어서 풀이해도 되지만 저는 dir라는 boolean타입 변수를 하나 선언해서 투포인터 식으로 앞과 뒤에서 문자열을 줄여가는 방식으로 코드를 작성했습니다.

3. 검증 (5분) - 1분

시간복잡도나 메모리에서 문제가 생길 부분은 없을 것 같고, 구상한 대로 잘 풀이된다면 코드도 문제없이 작동할 겁니다.

4. 풀이 (30분) - 25분

문제의 이해와 계획은 금방 끝났지만 코드 작성에선 시간을 꽤 사용했습니다. 

반복문을 복잡하게 사용하다 보니 디버깅을 사용해서 제대로 동작하는지 검증을 철저히 했습니다.

5. 채점, 디버깅

다행히 제출은 한 번에 통과했습니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

		char[] s1 = br.readLine().toCharArray();
		char[] s2 = br.readLine().toCharArray();

		int N = s2.length - s1.length;

		int front = 0, back = s2.length - 1;
		boolean dir = true;

		for (int n = 0; n < N; n++) {
			if (dir) {
				if (s2[back] == 'A') {
					back--;
				} else {
					back--;
					dir = false;
				}
			} else {
				if (s2[front] == 'A') {
					front++;
				} else {
					front++;
					dir = true;
				}
			}
		}

		boolean answer = true;

		if (dir) {
			for (int n = 0; n < s1.length; n++) {
				if (s1[n] != s2[front + n]) {
					answer = false;
					break;
				}
			}
		} else {
			for (int n = 0; n < s1.length; n++) {
				if (s1[n] != s2[back - n]) {
					answer = false;
					break;
				}
			}
		}

		if (answer) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}
}

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

https://www.acmicpc.net/problem/15810

1. 이해 (5분) - 1분

문제도 깔끔하고 이해에 어려운 부분도 없어 금방 이해를 마쳤습니다.

정답이 가능한 범위가 무척 넓은데 여기서 이분 탐색 문제임을 유추했습니다. 

(최악의 경우 스태프 1명이 100만분 마다 풍선 하나를 만들고, 이를 100만 개 불어야 하면.... 1조가 정답이다!) 

2. 계획 (5분) - 1분

문제를 이해한 대로 이분탐색을 통해 풀이할 계획을 세웠습니다.

이분 탐색에선 초기값을 잡는 것이 중요한데, 정답의 최댓값은 가장 빨리 풍선을 부는 스태프가 전부 부는 경우보다 작기 때문에 그 값을 최댓값으로 놓았습니다.

최솟값과 최댓값 사이의 중간값을 잡고, 이 값이 정답이 가능한 수인지를 확인합니다.

중간값을 각 스태프들이 풍선을 부는데 걸리는 시간으로 나누면 그 시간에 스태프들이 불 수 있는 풍선의 개수가 나오고 그 값을 전부 합치면 이 시간에 가능한 풍선의 개수가 나옵니다! 

풍선의 갯수를 주어진 M과 비교해서 크거나 같으면 정답이 중간값이거나 더 아래에 존재하므로 이분 탐색의 최댓값을 중간값으로 바꾸고 풍선이 부족하면 중간값 위에 정답이 존재하므로 최솟값을 중간값으로 바꿔줍니다.

3. 검증 (5분) - 3분

이분탐색 문제는 기본적으로 정답의 범위가 크기 때문에 오버플로우가 자주 발생합니다.

본 문제에서도 int의 범위는 넘을것이 딱 보였기 때문에 문제 전체에서 long을 사용하기로 했습니다.

(JAVA 언어의 long은 C, C++ 등의 longlong과 같습니다.)

4. 풀이 (30분) - 8분

이분탐색 코드는 생각해내기가 어렵지 코드량과 작성 자체는 어렵지 않기 때문에 금방 작성을 마쳤습니다.

하지만 이분탐색의 마수가 또다시 저를 괴롭히니...

5. 채점, 디버깅 (+20분)

여러 번의 오답을 맞으면서 디버깅 시간이 길어졌습니다.

문제 풀이의 접근과 코드의 논리에는 문제가 없으나, 이분 탐색의 양 극단의 값 중에서 정답을 고르는 부분에 문제가 있어 예외가 발생하는 것 같았습니다. (테스트 케이스 62%쯤에서 오답 처리되었습니다.)

검색을 통해 유익한 글을 찾아... 이분 탐색을 다시 이해하고 코드를 제출해 통과했습니다.

핵심 로직은 건드린 게 없으니, 예상대로 정답을 고르는 부분에서 문제가 있었던 것 같습니다.

https://www.acmicpc.net/blog/view/109

상당히 유익한 글이고 이분 탐색 문제 풀이에서 발생하는 오답을 잡아주기 때문에 저와 비슷한 어려움을 겪으시는 분들은 꼭 읽어보시길 추천드립니다.

구현은 쉽지만 오류 찾기가 어려운 이분 탐색 문제였습니다. 감사합니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;

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

		st = new StringTokenizer(br.readLine());
		long N = Integer.parseInt(st.nextToken());
		long M = Integer.parseInt(st.nextToken());
		long[] staffs = new long[(int) N];

		st = new StringTokenizer(br.readLine());
		long min = Integer.MAX_VALUE;
		for (int n = 0; n < N; n++) {
			staffs[n] = Integer.parseInt(st.nextToken());
			min = Math.min(min, staffs[n]);
		}
		
		long left = 0;
		long right = min * M;
		
		while(left+1 < right) {
			long center = (left + right)/2;
			long balloon = 0;
			
			for (int n = 0; n < N; n++) {
				balloon += (center / staffs[n]);
			}
			
			if(balloon >= M) {
				right = center;
			}else {
				left = center;
			}
		}
		
		System.out.println(right);
	}
}