da9dac

문제

접근 방식

최대 8*8 배열이라 백트래킹 + BFS로 무식하게 풀 수 있는 문제다.

벽을 3개 이하로 세우는 것이 아니고 무조건 3개를 다 세워야하기 때문에

벽을 3개 추가했을 때마다 BFS를 진행해주면 된다.

BFS는 바이러스가 있는 위치를 모두 큐에 넣어준 후에

0인 부분만 탐색을 진행하면서 카운트를 해주고

n * m에서 카운트를 빼주면 바이러스가 퍼지지 않은 지역의 넓이를 알 수 있다.

풀이

public class Main {

	static int n, m, max = 0, total;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int[][] map;
	static boolean[][] isVisited;
	static Queue<Pair> q = new ArrayDeque<>();

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

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		total = n * m;

		map = new int[n][m];
		isVisited = new boolean[n][m];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		solve(0);

		System.out.println(max);
	}

	static void solve(int wall) {
		if (wall == 3) {
			bfs();
			return;
		}

		for (int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if (map[i][j] != 0) continue;
				map[i][j] = 1;
				solve(wall + 1);
				map[i][j] = 0;
			}
		}
	}

	static void bfs() {
		int virusAndWalls = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int cur = map[i][j];
				if (cur == 1) {
					virusAndWalls++;
					continue;
				}

				if (cur == 2) {
					isVisited[i][j] = true;
					virusAndWalls++;
					q.offer(new Pair(i, j));
				}
			}
		}

		while (!q.isEmpty()) {
			Pair cur = q.poll();

			for (int dir = 0; dir < 4; dir++) {
				int x = cur.x + dx[dir];
				int y = cur.y + dy[dir];

				if(x < 0 || x >= n || y < 0 || y >= m) continue;
				if(isVisited[x][y] || map[x][y] != 0) continue;

				isVisited[x][y] = true;
				virusAndWalls++;
				q.offer(new Pair(x, y));
			}
		}

		for (int i = 0; i < n; i++) {
			Arrays.fill(isVisited[i], false);
		}

		max = Math.max(max, total - virusAndWalls);
	}

	static class Pair {
		int x, y;

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

문제

접근 방식

짝수 명의 직원들을 절반씩 나누어 두 팀으로 구성할 때

두 팀의 능력치 차이가 가장 적은 경우를 구해야 한다.

각 팀을 모두 조합할 필요는 없고 한 팀만 구해도 되는데

한쪽팀만 구하면 반대팀은 자동으로 구성되기 때문이다.

백트래킹을 이용해 절반인 n/2까지 재귀를 호출하며

팀을 짜주고 n/2일 때 현재까지 기록으로

각 팀간의 점수차를 구해주면 된다.

즉, 절반의 팀을 구하는 메서드와

각 팀의 점수를 계산하고 차이를 구하는 메서드가 필요하다.

풀이

class Main {
    
    static int n, m;
	static int min = Integer.MAX_VALUE;
	static int[][] stats;
	static boolean[] isUsed;

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

		n = Integer.parseInt(br.readLine());
		m = n/2;

		stats = new int[n][n];
		isUsed = new boolean[n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < n; j++) {
				stats[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		solve(0, 0);

		System.out.println(min);
	}

	static void solve(int s, int start) {
		if (s == m) {
			calculate();
			return;
		}

		for (int i = start; i < n; i++) {
			if (isUsed[i]) continue;
			if (s == 0 && i > 0) break;
			isUsed[i] = true;
			solve(s + 1, i + 1);
			isUsed[i] = false;
		}
	}

	static void calculate() {
		int start = 0;
		int link = 0;

		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (isUsed[i] == isUsed[j]) {
					if (isUsed[i]) {
						start += (stats[i][j] + stats[j][i]);
					} else {
						link += (stats[i][j] + stats[j][i]);
					}
				}
			}
		}

		min = Math.min(min, Math.abs(start - link));
	}
}

문제

접근 방식

수가 최대 11개까지만 있어서 무식하게 풀어도 가능한

기본적인 백트래킹 문제다.

간단한 과정은 다음과 같다.

1. 각 연산자의 사용횟수가 아직 남아있는지 확인
2. 남아있다면 사용횟수를 1 감소시킨 후 재귀호출
3. 자기 자신으로 돌아오면 감소시킨 사용횟수 복구
4. 식을 모두 사용했으면 현재 값을 비교해 최대최소 기록

풀이

public class Main {

	static int n, plus, minus, multi, div;
	static int min = 1000000001, max = -1000000001;
	static int[] arr;
	static boolean[] isUsed;

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

		n = Integer.parseInt(br.readLine());
		arr = new int[n];
		isUsed = new boolean[n];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		st = new StringTokenizer(br.readLine());

		plus = Integer.parseInt(st.nextToken());
		minus = Integer.parseInt(st.nextToken());
		multi = Integer.parseInt(st.nextToken());
		div = Integer.parseInt(st.nextToken());

		solve(arr[0], 2);

		sb.append(max).append("\n").append(min);

		System.out.println(sb);
	}

	static void solve(int result, int cur) {
		if(cur > n) {
			min = Math.min(min, result);
			max = Math.max(max, result);
			return;
		}

		if (plus != 0) {
			plus--;
			solve(result + arr[cur - 1], cur + 1);
			plus++;
		}

		if (minus != 0) {
			minus--;
			solve(result - arr[cur - 1], cur + 1);
			minus++;
		}

		if (multi != 0) {
			multi--;
			solve(result * arr[cur - 1], cur + 1);
			multi++;
		}

		if (div != 0) {
			div--;
			solve(result / arr[cur - 1], cur + 1);
			div++;
		}

	}
}

문제

접근 방식

현재 큐에 남아 있는 우선순위 중 가장 큰 값이 등장하기 전까지는

빼서 다시 맨 뒤에 넣어주어야 한다.

그렇게 계속 진행하다 현재 값이 가장 큰 값이거나 같다면 빼주고

카운트를 1 증가시켜주면 된다.

다만 값을 뺄 때 목표로 하던 값인지를 확인해야 하는데

이를 객체를 하나 생성하여 우선순위와 목표인지 여부를 기록해

큐에 넣고 돌아주면 편리하다.

현재 가장 큰 값을 체크하기 위해 우선순위 큐를 사용하였지만

배열에 받아두고 정렬을 하여 값을 꺼낼 때마다

바라보고 있는 인덱스를 1씩 감소시켜도 문제없다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		Queue<Pair> q;
		PriorityQueue<Integer> pq;
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine());

		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());

			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());

			st = new StringTokenizer(br.readLine());

			q = new ArrayDeque<>();
			pq = new PriorityQueue<>((x1, x2) -> x2 - x1);

			for (int i = 0; i < n; i++) {
				int x = Integer.parseInt(st.nextToken());

				q.offer(new Pair(x, i == m));
				pq.offer(x);
			}

			int cnt = 0;

			while(!q.isEmpty()) {
				int max = pq.peek();
				Pair cur = q.poll();

				if (cur.num < max) {
					q.offer(cur);
					continue;
				}

				cnt++;

				if (cur.isTarget) break;
				pq.poll();
			}

			sb.append(cnt).append("\n");
		}

		System.out.println(sb);
	}

	static class Pair {
		int num;
		boolean isTarget;

		public Pair(int num, boolean isTarget) {
			this.num = num;
			this.isTarget = isTarget;
		}
	}
}

문제

접근 방식

기본적인 BFS 탐색을 사용한 최단거리 문제로

2차원 배열이 아닌 3차원 배열이라는 부분만 다르기 때문에

기존에는 동서남북으로만 탐색 했다면 위층과 아래층으로

올라가거나 내려가는 탐색도 포함시켜 주면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int l, r, c;
		String[] input;
		char[] chars;
		boolean[][][] isVisited;
		char[][][] building;
		int[] dl = {0, 0, 0, 0, 1, -1};
		int[] dr = {0, 0, 1, -1, 0, 0};
		int[] dc = {1, -1, 0, 0, 0, 0};

		while (true) {
			input = br.readLine().split(" ");

			l = Integer.parseInt(input[0]);
			r = Integer.parseInt(input[1]);
			c = Integer.parseInt(input[2]);
			boolean isEscaped = false;

			if (l == 0 && r == 0 && c == 0) break;

			building = new char[l][r][c];
			isVisited = new boolean[l][r][c];

			Queue<Me> q = new ArrayDeque<>();

			for (int i = 0; i < l; i++) {
				for (int j = 0; j < r; j++) {
					chars = br.readLine().toCharArray();
					for (int k = 0; k < c; k++) {
						if (chars[k] == 'S') q.offer(new Me(i, j, k, 0));
						building[i][j][k] = chars[k];
					}
				}
				br.readLine();
			}

			while (!q.isEmpty()) {
				Me cur = q.poll();

				for (int dir = 0; dir < 6; dir++) {
					int nl = cur.l + dl[dir];
					int nr = cur.r + dr[dir];
					int nc = cur.c + dc[dir];

					if (nl < 0 || nl >= l || nr < 0 || nr >= r || nc < 0 || nc >= c) continue;
					if (isVisited[nl][nr][nc] || building[nl][nr][nc] == '#') continue;

					if (building[nl][nr][nc] == 'E') {
						isEscaped = true;
						sb.append("Escaped in ").append(cur.move + 1).append(" minute(s).").append("\n");
						break;
					}

					isVisited[nl][nr][nc] = true;
					q.offer(new Me(nl, nr, nc, cur.move + 1));
				}

				if (isEscaped) break;
			}

			if (!isEscaped) sb.append("Trapped!").append("\n");
		}

		System.out.println(sb);
	}

	private static class Me {
		int l, r, c, move;

		public Me(int l, int r, int c, int move) {
			this.l = l;
			this.r = r;
			this.c = c;
			this.move = move;
		}
	}
}

문제

접근 방식

생긴 거만 봐도 DFS 문제인 것을 알 수 있지만

DFS만으로 풀고 제출하면 시간초과가 발생한다.

DFS에 DP까지 활용해야 하는데 아래의 경우를 생각해 보자

이 사진에서 오른쪽 경우는 왼쪽이 이미 방문한 20부터의 순서를 그대로 반복하는데

이미 갔던 길을 다시 가는 거라면 굳이 또 갈 필요가 없이

해당 구간으로 가는 길에 계산된 값을 그대로 사용하면 된다.

즉, 처음 가는 구간이라면 계속해서 도착 지점에 방문할 때까지 탐색하고

탐색 중에 이미 방문한 곳이라면 그 구간에 저장되어 있는 값을 더 해준다.

방문 여부를 기록할 불리언 배열은 필요 없고

2차원의 DP 테이블에 값이 채워져 있으면

기존에 방문한 것을 알 수 있기 때문에 이를 활용해서

탐색을 진행해 주면 된다.

이번 문제가 아니더라도 반복된 구간을 탐색하는 경우라면

이런 메모이제이션 방식을 사용해도 좋을 것 같다.

풀이

class Main {
    
    static int m, n;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int[][] arr, dp;

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

		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());

		arr = new int[m + 1][n + 1];
		dp = new int[m + 1][n + 1];

		for (int i = 1; i <= m; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 1; j <= n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
        
        for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = -1;
			}
		}

		System.out.println(dfs(1, 1));
	}

	static int dfs(int cx, int cy) {
		if (cx == m && cy == n) {
			return 1;
		}

		if (dp[cx][cy] != -1) {
			return dp[cx][cy];
		}

		dp[cx][cy] = 0;

		for (int dir = 0; dir < 4; dir++) {
			int x = cx + dx[dir];
			int y = cy + dy[dir];

			if (x < 0 || x > m || y < 0 || y > n) continue;
			if (arr[x][y] < arr[cx][cy]) {
				dp[cx][cy] += dfs(x, y);
			}
		}

		return dp[cx][cy];
	}
}

문제

접근 방식

1차원 배열의 구간합 원리를 2차원 배열에 적용하면 풀 수 있는 문제다.

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

위와 같은 배열이 주어졌을 때 2,2 부터 3,4까지의 구간합을 구하려면

2,2 ~ 2,4의 구간합 + 3,2 ~ 3,4의 구간합을 더해주면 된다.

1 3 6 10
2 5 9 14
3 7 12 18
4 9 15 22

위처럼 각 행마다의 누적합을 구해둔 후에

이 누적합을 이용해 각 행의 특정 부분의 구간합을 구해주면 된다.

예를 들어 2,2 ~ 2,4까지의 구간합은

2,4까지의 누적합에서 2,1의 누적합을 뺀 것이고

3,2 ~ 3,4까지의 구간합은

3,4까지의 누적합에서 3,1의 누적합을 뺀 것이다.

결국 x축을 기준으로 시작 x축부터 끝나는 x축까지 반복하며

각 행의 구간합을 구하여 더해주면 된다.

풀이

public class Main {

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		long[][] dp = new long[n + 1][n + 1];

		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= n; j++) {
				dp[i][j] = dp[i][j - 1] + Integer.parseInt(st.nextToken());
			}
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			int sx = Integer.parseInt(st.nextToken());
			int sy = Integer.parseInt(st.nextToken());
			int ex = Integer.parseInt(st.nextToken());
			int ey = Integer.parseInt(st.nextToken());

			long result = 0;

			for (int i = sx; i <= ex; i++) {
				result += (dp[i][ey] - dp[i][sy - 1]);
			}

			sb.append(result).append("\n");
		}

		System.out.println(sb);
	}
}

문제

접근 방식

각 자리의 수마다 경우의 수를 이전 자리의 수들을 활용해가며

DP 테이블을 채워주면 되는 간단한거 같은 문제지만

예외 케이스가 머리를 아프게 한다.

우선 11111111과 같은 일반적인 경우를 살펴보겠다.

위의 표는 첫 자리부터 각 자리수마다 만들 수 있는 경우의 수로

3번째 자리의 수에 올 수 있는 경우의  수는

3번째 자리를 독립적으로 사용한 경우나

2번째 자리와 합쳐서 두 자리 수를 만든 경우를 합친 것으로

규칙을 찾아보면 피보나치의 점화식과 같은

dp[i] = dp[i-2] + dp[i-1] 인 것을 알 수 있다.

하지만 이건 모든 수들이 일반적일 때의 경우로

다음과 같이 조심해야 할 부분이 있다.

1. 0으로 시작하는 경우
2. 00인 경우
3. 26보다 큰 경우
4. 10 미만인 경우
5. 10, 20인 경우
6. 마지막 자리가 0이고 30 이상인 경우

0123456

첫 번째 경우부터 살펴보면

0이 처음에 등장하여 00이나 01 같은 잘못된 경우가 발생할 수 밖에 없다.

0이 중간에 등장한다면 10이나 20 같은 2자리 숫자로라도 만들 수 있지만

처음에 등장하면 앞에 붙여줄 숫자가 없으니 살릴 방법이 없다.

1001

다음은 0이 연속으로 등장하는 경우로

이건 당연히 무슨 수를 써도 정상적인 수를 만들 수 없다.

127

다음은 26보다 큰 숫자가 등장하는 경우로 위의 경우에는

1 + 2 + 7 과 12 + 7 두 가지 경우를 만들 수 있다.

1 + 27 같은건 만들 수 없기 때문에 dp[i-2]의 값은 필요가 없어

dp[i] = dp[i-1]이 된다.

109

마찬가지로 10보다 작은 0으로 시작하는 경우도

1 + 0 + 9는 불가능하고 10 + 9만 가능하니

dp[i-2]의 값은 필요가 없어 dp[i] = dp[i-1]이 된다.

1101
1201

다음은 10 혹은 20의 경우를 생각해보자

0은 무조건 이전의 숫자인 1이나 2와 합쳐야지만

정상적인 수로 존재할 수 있기 때문에

위의 두 경우와 반대로 dp[i-1]이 필요가 없어

dp[i] = dp[i-2] 가 된다.

130

그렇다면 마지막 자리가 0이고 30 이상이면 어떻게 될까?

0은 혼자서는 온전한 수가 될 수 없어 무조건 이전의 수와 합쳐야하는데

합쳐서 10이나 20이 된다면 상관 없지만 30, 40, ..., 90이라면

26이상의 수라 알파벳으로 바꿀 수 없는 수가 되버린다.

이는 잘못된 경우이기 때문에 0을 출력해줘야 한다.

위의 경우들을 모두 예외 처리 해주면서 테이블을 채워주기만 하면 된다.

풀이

public class Main {

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

		String secret = br.readLine();

		if (secret.charAt(0) == '0') {
			System.out.println(0);
			return;
		}

		int len = secret.length();
		long[] dp = new long[len + 1];

		dp[0] = 1;
		dp[1] = 1;

		for (int i = 2; i <= len; i++) {
			int x = Integer.parseInt(secret.substring(i - 2, i));

			if (x == 0) {
				System.out.println(0);
				return;
			}

			if (i == len && x % 10 == 0 && x > 26) {
				System.out.println(0);
				return;
			}

			if (x > 26 && x % 10 == 0) {
				System.out.println(0);
				return;
			}

			if (x > 26 || x < 10) {
				dp[i] = dp[i-1];
			} else if (x % 10 == 0) {
				dp[i] = dp[i-2];
			} else {
				dp[i] = (dp[i-1] + dp[i-2]) % 1000000;
			}
		}

		System.out.println(dp[len]);
	}
}