Pearlii-Log

문제 풀이 날짜: 2023.09.05
포스트 작성일: 2023.09.11

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 16401번: 과자 나눠주기 (실버2)

키워드

이분 탐색, 매개변수 탐색

풀이 접근법

• 이분탐색의 일종인 매개 변수 탐색(Parametric Search)을 이용하는 문제이다.
• 조카의 수보다 과자의 수가 적다면 과자를 1 단위까지 쪼갤 수 있다.
  • 단, 과자를 합칠 수는 없으므로 항상 큰 것을 쪼개서 작게 만들어야 한다.
• 나눠줄 수 있는 인원이 총 몇 명인지는 나눗셈의 몫으로 구한다.
• 길이 몇 짜리를 나누어줄 지는 이분탐색으로 찾아나간다. 개수가 많이 나왔다면 나눠줄 길이를 늘리고, 개수가 너무 적게 나왔다면 나눠줄 길이를 줄인다.

코드

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

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(), " ");

		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		int[] snacks = new int[N];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < N; i++) {
			snacks[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(snacks);
		
		int result = 0;
		int maxSize = snacks[N - 1];
		
		int count = 0;
		for(int s : snacks) {
			count += s / maxSize; //초기 길이로 몇 명에게 줄 수 있는지 센다.
		}
		
		if(count >= M) {
			System.out.print(maxSize);
			return;
		}
		
		int left = 1;
		int right = maxSize;
		while(left <= right) {
			int mid = (left + right) / 2;
			
			count = 0;
			for(int s : snacks) {
				count += s / mid; //현재 길이로 몇 명에게 줄 수 있는지 센다.
			}
			
			if(count >= M) {
				result = Math.max(mid, result);
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		
		System.out.print(result);
	}

}

참고한 링크

• https://se-jung-h.tistory.com/entry/BOJC-백준-16401-과자-나눠주기
• https://velog.io/@kmh9250/백준16401-과자-나눠주기

git 링크

(git 링크 첨부)

문제 풀이 날짜: 2023.09.01
포스트 작성일: 2023.09.11

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 15683번: 감시 (골드4)

키워드

완전 탐색, 백트래킹

풀이 접근법

• 사각지대의 최소 크기 ⇒ matrix에 남아있는 0의 개수가 최소가 되도록 한다.
• 각 CCTV마다 설치 가능한 방향을 완전탐색으로 찾는다.
  • 1. CCTV의 좌표를 리스트로 취합한다.
  • 2. 가능한 방향마다 회전시켜서 감시 범위를 설정한다.
    • 중복되는 감시 범위를 체크/체크해제 해야 하므로 scope 배열은 int[ ][ ]로 선언한다.
  • 3. 다음 재귀를 탐색한다.
  • 4. 재귀에서 리턴받았다면 감시 범위를 해제시킨다.
  • 5. 기저사례에 도달했다면 배열에 남은 0의 개수(카메라가 닿지 않는 곳)를 센다.
• 카메라의 회전은 어떻게 구현할까?
  • 각 CCTV 방향별로 switch문을 통해 체크한다 ⇒ 각 방향마다 모두 배열에 표시해본 후 유망한 것을 찾는다.

코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	private static final int BLANK = 0;
	private static final int WALL = 6;
	
	private static int N;
	private static int M;
	
	private static int count;
	private static int min = Integer.MAX_VALUE;
	
	private static int[][] matrix;
	private static int[][] scopes;
	
	private static List<Point> cameras = new ArrayList<>();
	
	private static int[] dr = {1, 0, -1, 0};
	private static int[] dc = {0, 1, 0, -1};
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] temp = br.readLine().split(" ");
		
		N = Integer.parseInt(temp[0]);
		M = Integer.parseInt(temp[1]);

		matrix = new int[N][M];
		scopes = new int[N][M];
		
		StringTokenizer st;
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < M; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
				
				//5번 카메라는 제외하고 add
				if(matrix[i][j] != BLANK && matrix[i][j] != WALL 
						&& matrix[i][j] != 5) {
					cameras.add(new Point(j, i));
				}
				
				if(matrix[i][j] != BLANK) {
					scopes[i][j] = -1; //사각지대에서 제외시킬 곳 기록
				}
			}
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(matrix[i][j] == 5) { //회전시킬 필요 없는 카메라는 미리 세팅한다.
					for(int dir = 0; dir < dr.length; dir++) {
						setScope(scopes, new Point(j, i), dir, 1);
					}
				}
			}
		}
		
		count = cameras.size(); //5번 카메라를 제외한 카메라의 수

		DFS(scopes, 0);
		
		System.out.println(min);
	}
	
	private static void DFS(int[][] scopes, int depth) {
		if(depth == count) {
			int result = 0;
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					if(scopes[i][j] == BLANK) result += 1;
				}
			}

			min = Math.min(result, min);
			
			return;
		}
		
		Point curr = cameras.get(depth);
		int r = curr.y;
		int c = curr.x;
		
		switch(matrix[r][c]) { //카메라 방향 별 시야 기록
			case 1: {
				for(int dir = 0; dir < dr.length; dir++) {
					setScope(scopes, curr, dir, 1);
					DFS(scopes, depth + 1);
					setScope(scopes, curr, dir, -1); //원복
				}
				break;
			}
			case 2: {
				for(int dir = 0; dir < dr.length / 2; dir++) {
					setScope(scopes, curr, dir, 1);
					setScope(scopes, curr, dir + 2, 1); //dir과 대칭 방향
					DFS(scopes, depth + 1);
					setScope(scopes, curr, dir, -1); //원복
					setScope(scopes, curr, dir + 2, -1);
				}
				break;
			}
			case 3: {
				for(int i = 0; i < dr.length; i++) {
					for(int j = i + 1; j < dr.length; j++) { //서로 다른 두 방향 i, j를 탐색 (대칭X)
						if(i == j || Math.abs(i - j) == 2) { continue; }
						setScope(scopes, curr, i, 1);
						setScope(scopes, curr, j, 1); //dir과 대칭 방향
						DFS(scopes, depth + 1);
						setScope(scopes, curr, i, -1); //원복
						setScope(scopes, curr, j, -1);
					}
				}
				break;
			}
			case 4: {
				for(int k = 0; k < dr.length; k++) {
					for(int dir = 0; dir < dr.length; dir++) {
						if(k == dir) { continue; } //k번째 방향을 제외한 세 방향 탐색
						setScope(scopes, curr, dir, 1);
					}
					
					DFS(scopes, depth + 1);
					
					for(int dir = 0; dir < dr.length; dir++) {
						if(k == dir) { continue; } //k번째 방향을 제외한 세 방향 탐색
						setScope(scopes, curr, dir, -1); //원복
					}
				}
				break;
			}
		}
		
	}
	
	private static void setScope(int[][] scope, Point start, int dir, int target) {
		int nr = start.y;
		int nc = start.x;
		while(true) {
			nr += dr[dir];
			nc += dc[dir];
			
			//벽이라면 탐색을 멈춘다.
			if(!isValid(nr, nc) || matrix[nr][nc] == WALL) { return; }
			
			//다른 숫자라면 계속 탐색한다. 0인 경우에만 target으로 덮어씌운다.
			if(matrix[nr][nc] == BLANK) { scope[nr][nc] += target; }
		}
	}

	private static boolean isValid(int nr, int nc) {
		return (nr > -1 && nc > -1 && nr < N && nc < M);
	}

}

git 링크

(git 링크 첨부)

문제 풀이 날짜: 2023.08.31
포스트 작성일: 2023.08.31

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 13023번: ABCDE (골드5)

키워드

DFS, 그래프 탐색

풀이 접근법

• A, B, C, D, E 라는 문자에 집중하기보다는, 그래프에서 연달아 4개 이상의 경로가 연결되어 있는지를 확인하면 된다. 즉, DFS의 depth가 4 이상이 되면 된다.
• 44%에서 틀렸습니다를 받은 적 있는데, 실패한 경로에 대한 탐색 기록 삭제하는 작업을 해주어야 한다. 이미 간 경로가 유망하지 않을 때, visited 표시를 복구해주어야 한다.
  • 그런데 이렇게 원복 해주면 방문했던 점을 재방문해서 시간 초과가 난다.
  • 따라서 이전 경로가 유망하지 않을 때만(false를 반환했을 때만) visited를 되돌려주고, 그렇지 않을 때는 그대로 둔다.

코드

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

public class Main {

	private static List<Integer>[] graph;
	private static boolean[] visited;
	
	private static int flag = 0;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] temp = br.readLine().split(" ");
		
		int N = Integer.parseInt(temp[0]);
		int M = Integer.parseInt(temp[1]);

		int[] from = {0, 1, 2, 3};
		int[] to = {1, 2, 3, 4};
		
		graph = new ArrayList[N];
		visited = new boolean[N];
		
		for(int i = 0; i < N; i++) {
			graph[i] = new ArrayList<>();
		}
			
		for(int i = 0; i < M; i++) {
			temp = br.readLine().split(" ");
			
			int v = Integer.parseInt(temp[0]);
			int u = Integer.parseInt(temp[1]);
			
			graph[v].add(u);
			graph[u].add(v);
		}
		
		for(int i = 0; i < N; i++) {
			visited[i] = true;
			DFS(i, 0);
			visited = new boolean[N];
		}
		
		System.out.println(flag);
	}

	private static boolean DFS(int start, int depth) {		
		if(depth >= 4) {
			flag = 1;
			return true;
		}
		
		for(int u : graph[start]) {
			if(!visited[u]) {
				visited[u] = true;
				if(!DFS(u, depth + 1)) {
					visited[u] = false;
				}
			}
		}
		
		return false;
	}
}

git 링크

https://github.com/jinju9553/23-CodingTest/blob/d37c971dcff078a725f78a2ce49db2b02ecde004/%EB%B0%B1%EC%A4%80/Gold/13023.%E2%80%85ABCDE/ABCDE.java

문제 풀이 날짜: 2023.08.27
포스트 작성일: 2023.08.30

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

SWEA 1767번: 프로세서 연결하기

키워드

백트래킹, 부분 집합

풀이 접근법

• 각 코어마다의 전선 방향을 결정하는 순열을 구하는 것이라고 생각하기 쉬운데, 입력이 7 ≤ N ≤ 12 이기 때문에 시간 초과가 난다. 사실상 코어의 순서는 중요하지 않기 때문에 순열을 고려할 필요가 없다.
  • 그럼에도 재귀(백트래킹)로 풀어야 하는 상황인데, 방문하지 않아도 되는 경우에 대해 가지치기를 잘 해주지 않아도 얄짤없이 시간 초과가 난다.
• 그렇다면 어떻게 최적화를 해야하는가?
  • 코어 리스트에 코어를 넣을때, 애초에 연결이 안 되는 코어(벽에 붙은 코어)는 고려하지 않아도 되므로 리스트에 넣지 않는다.
  • 남은 코어를 전부 더해도 현재까지 계산한 maxCore보다 작을 때, 그 이후 탐색을 중단(return)한다. (가지 치기)
    • 즉, 재귀의 최대 depth까지 도달하기 전에 가지치기가 되어야 한다. 가능한 많은 개수의 코어를 연결했을 때의 길이만 필요한데, maxCore를 넘기는 경우를 구하지 못한다면 애초에 그 재귀를 지속할 필요가 없다.

• 부분 집합으로 포함시킬 코어를 정한다. 코어를 선택할 것이라면 4방향으로 연결을 시도(setStatus() 메소드)해보고, 선택하지 않는다면 연결을 시도하지 않고 즉시 다음 재귀로 넘어간다.
  • 모든 전선을 다 놓지 말고, 어떤 방향으로 전선 놓기가 가능한지 판단한 후에 배치가 가능한 전선만 놓는다. 전선을 놓았다면 표시(visit)를 한다.
  • 기저 사례: 부분집합이 완성되었을 때는 연결된 코어의 개수와 최소 길이를 갱신한다.

코드

package swea.Ad.swea1767;

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

public class Solution {

	private static int N, totalCount;
	private static int maxCore, minLength;
	
	private static int[] dr = {-1, 1, 0, 0};
	private static int[] dc = {0, 0, -1, 1};
	
	private static int[][] board;
	private static List<Core> cores;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for (int test_case = 1; test_case <= T; test_case++) {
			N = Integer.parseInt(br.readLine());
			
			totalCount = 0;
			maxCore = 0;
			minLength = Integer.MAX_VALUE;
			
			board = new int[N][N];
			cores = new ArrayList<>();
			
			StringTokenizer st;
			for(int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for(int j = 0; j < N; j++) {
					board[i][j] = Integer.parseInt(st.nextToken());
					
					if(isBorder(i, j) && board[i][j] == 1) { continue; }
					
					if(board[i][j] == 1) {
						cores.add(new Core(i, j));
						totalCount++;
					}
				}
			}
			
			permutation(0, 0);
			
			sb.append("#").append(test_case).append(" ").append(minLength).append("\n");
		}
		
		System.out.println(sb);
	}

	private static boolean isBorder(int r, int c) {
		return r == 0 || r == N - 1 || c == 0 || c == N - 1;
	}

	/**
	 * @param depth : 재귀의 깊이
	 * @param index : 고려해야 할 코어의 번호
	 * @param coreCount : 지금까지 연결된 코어의 수
	 */
	private static void permutation(int depth, int coreCount) {
		//가지치기: 현재까지 연결된 코어 수 + 남은 코어 수 < 임시 최대 코어 수라면
		//예: 이미 7개짜리 답을 구해놨는데 6개짜리 답밖에 못 구하는 상황이면 가지치기
		if(coreCount + (totalCount - depth) < maxCore) {
			return; 
		}
		
		if(depth == totalCount) {
			int res = getLength();
			
			if(maxCore < coreCount) {
				maxCore = coreCount;
				minLength = res;
			} else if(maxCore == coreCount) {
				minLength = Math.min(res, minLength);
			}
			return;
		}
		
		Core core = cores.get(depth);
		int r = core.row;
		int c = core.col;
		
		//1.현재 코어를 선택
		for(int dir = 0; dir < 4; dir++) {
			if(!isAvailable(r, c, dir)) { continue; }
			
			setStatus(r, c, dir, 2); //전선 놓기
			
			permutation(depth + 1, coreCount + 1);
			
			setStatus(r, c, dir, 0); //전선 지우기
		}
		
		//2.현재 코어를 선택하지 않음
		permutation(depth + 1, coreCount);
	}

	private static int getLength() {
		int len = 0; //전선을 센다.
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(board[i][j] == 2) {
					len++;
				}
			}
		}
		
		return len;
	}

	private static void setStatus(int r, int c, int dir, int status) {
		int nr = r;
		int nc = c;
		
		while(true) {
			nr += dr[dir];
			nc += dc[dir];
			
			if(nr < 0 || nc >= N || nc < 0 || nc >= 0) {
				break;
			}
			
			board[nr][nc] = status;
		}
	}

	private static boolean isAvailable(int r, int c, int dir) {
		int nr = r;
		int nc = c;
		
		while(true) {
			nr += dr[dir];
			nc += dc[dir];
			
			if(nr < 0 || nc >= N || nc < 0 || nc >= 0) { break; }
			
			if(board[nr][nc] != 0) { return false; } //다른 코어를 만나거나 전선이 있다면
		}
		
		return true;
	}
}

class Core {
	int row;
	int col;
	
	public Core(int row, int col) {
		this.row = row;
		this.col = col;
	}
}

git 링크

(git 링크 첨부)

문제 풀이 날짜: 2023.08.30
포스트 작성일: 2023.08.30

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 17070번: 파이프 옮기기 1 (골드5)

키워드

동적 계획법

풀이 접근법

• 좌표에 따라 값을 채워 넣는 2차원 DP문제
• 파이프의 모양이 계속 변하므로 매 칸마다 파이프의 상황을 고려해서 각기 다르게 DP를 채워넣어야 한다.
• 즉, (현재 지점까지 올 수 있는 경우의 수 + 현재의 파이프의 방향) 두 가지 정보를 고려해야 한다.
• 그런데 파이프의 모양에 따라 이전 값을 끌어다 쓸 수 있는 경우는 한정적이다.
  • 현재 모양이 - 라면 왼쪽, 대각선 위의 DP만 가져올 수 있다.
  • 현재 모양이 | 라면 윗쪽, 대각선 위의 DP만 가져올 수 있다.
  • 현재 모양이 / 라면 왼쪽, 대각선 위, 윗쪽의 DP를 가져올 수 있다.
• 이 규칙에 맞추어 Bottom-Up으로 DP값을 구해준다.
• 벽이 세워진 곳을 DP 계산에 포함시키지 않도록 주의한다.

코드

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

public class Main {

	private static final int HOR = 0;
	private static final int DIAG = 1;
	private static final int VERT = 2;

	private static int N;

	private static int[][] matrix;
	private static int[][][] DP;

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

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

		matrix = new int[N][N];
		DP = new int[3][N][N]; // 파이프의 방향: 0, 1, 2

		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		DP[HOR][0][0] = 1;
		DP[HOR][0][1] = 1;

		for (int i = 0; i < N; i++) {
			for (int j = 2; j < N; j++) {
				if(matrix[i][j] == 1) {
					continue;
				}
				
				if (i - 1 >= 0 && matrix[i - 1][j] != 1) { // 윗쪽에서 밀 수 있다면
					DP[VERT][i][j] += (DP[VERT][i - 1][j] + DP[DIAG][i - 1][j]);
				}

				if (j - 1 >= 0 && matrix[i][j - 1] != 1) { // 왼쪽에서 밀 수 있다면
					DP[HOR][i][j] += (DP[HOR][i][j - 1] + DP[DIAG][i][j - 1]);
				}

				if (i - 1 >= 0 && j - 1 >= 0 && matrix[i - 1][j] != 1 && matrix[i][j - 1] != 1 && matrix[i - 1][j - 1] != 1) { // 대각선에서 밀 수 있다면
					DP[DIAG][i][j] += (DP[HOR][i - 1][j - 1] + DP[VERT][i - 1][j - 1] + DP[DIAG][i - 1][j - 1]);
				}
			}

		}

		int result = 0;
		for (int k = 0; k < 3; k++) {
			result += DP[k][N - 1][N - 1];
		}

		System.out.println(result);
	}
}

git 링크

https://github.com/jinju9553/23-CodingTest/blob/0a9ccbe8b196e2a4be747761ba50ef01f903a74d/%EB%B0%B1%EC%A4%80/Gold/17070.%E2%80%85%ED%8C%8C%EC%9D%B4%ED%94%84%E2%80%85%EC%98%AE%EA%B8%B0%EA%B8%B0%E2%80%851/%ED%8C%8C%EC%9D%B4%ED%94%84%E2%80%85%EC%98%AE%EA%B8%B0%EA%B8%B0%E2%80%851.java

문제 풀이 날짜: 2023.08.30
포스트 작성일: 2023.08.30

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 1600번: 말이 되고픈 원숭이 (골드3)

키워드

BFS, 동적 계획법

풀이 접근법

• 말 처럼 움직이는 횟수는 총 K회로 제한된다. 그런데 먼저 K회를 모두 말 처럼 움직여버리면 다음의 케이스에서 더 이상 나아갈 수 없는 경우가 생긴다.

  2
  10 2
  0 0 1 0 0 1 0 0 1 0
  0 0 1 1 0 0 0 0 1 0

• 즉, 말처럼 움직인 경우와 원숭이가 그냥 이동한 경우를 구분하지 못하면 반례가 생긴다. 그렇기 때문에 각 탐색 때마다 말처럼 움직인 경우, 그냥 이동한 경우를 나누어 탐색한다.
• 즉, 말처럼 0-k번 움직인 경우의 수를 모두 별도의 배열로 관리한다. 마지막에는 이렇게 0부터 k번까지 말처럼 움직인 경우의 수 중에서 가장 최소인 값을 가져온다.
• DP 배열은 현재의 위치(r, c)와 말 처럼 움직인 횟수(k)의 정보를 동시에 가져야 하므로 3차원 배열로 선언한다.
• 메모리 초과가 쉽게 발생할 수 있으므로 위처럼 이미 구했던 점을 queue에 넣지 않도록 주의한다.
  • visited 배열 또한 DP 배열과 같은 원리로 선언하여, 원숭이가 k번째로 말처럼 움직였을 때의 DP값을 이미 구한 경우를 스킵시키는 용도로 사용한다.

코드

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

public class Main {

	private static int K;
	private static int W;
	private static int H;

	private static int[] hdr = { 2, 2, -2, -2, 1, -1, 1, -1 };
	private static int[] hdc = { 1, -1, 1, -1, 2, 2, -2, -2 };

	private static int[] mdr = { 0, 1, 0, -1 };
	private static int[] mdc = { 1, 0, -1, 0 };

	private static int[][] board;
	private static int[][][] DP;
	private static boolean[][][] visited;

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

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

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

		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());

		board = new int[H][W];
		DP = new int[H][W][K + 1]; //(r,c)에 다다를 때까지, K번만큼 말 처럼 움직인 결과를 기록
		visited = new boolean[H][W][K + 1];

		for (int i = 0; i < H; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < W; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				
				for(int k = 0; k <= K; k++) {
					DP[i][j][k] = Integer.MAX_VALUE;
				}
			}
		}

		BFS(0, 0);

		int result = Integer.MAX_VALUE;
		for(int k = 0; k <= K; k++) { //k를 쓴 횟수마다 최소값을 따야 함
			result = Math.min(result, DP[H - 1][W - 1][k]);
		}
		
		if (W - 1 == 0 && H - 1 == 0) {
			result = 0;
		}
		else if (result == Integer.MAX_VALUE) {
			result = -1;
		}
		
		System.out.println(result);
	}

	private static void BFS(int startR, int startC) {
		Queue<Node> queue = new ArrayDeque<>();

		visited[startC][startR][0] = true;
		queue.add(new Node(startC, startR, 0));
		
		while (!queue.isEmpty()) {
			Node n = queue.poll();

			int nr = 0;
			int nc = 0;
			if (n.k < K) {
				// 1.말처럼 움직여보기 ==> K번만 움직일 수 있다.
				for (int i = 0; i < hdr.length; i++) {
					nr = n.row + hdr[i];
					nc = n.col + hdc[i];

					if (nr == 0 && nc == 0) {
						continue;
					}

					if (!isValid(nr, nc, n.k + 1)) { //k + 1번째 이동을 이미 처리했다면 continue
						continue;
					}

					// DP 갱신을 위해 방문체크 하지 않음
					if (DP[nr][nc][n.k + 1] >= DP[n.row][n.col][n.k] + 1) { // 이동횟수가 작거나 같다면
						DP[nr][nc][n.k + 1] = (DP[n.row][n.col][n.k] == Integer.MAX_VALUE) 
								? 1 : DP[n.row][n.col][n.k] + 1;
												
						if (nr == H - 1 && nc == W - 1) { return; }
						
						visited[nr][nc][n.k + 1] = true;
						queue.add(new Node(nr, nc, n.k + 1));
					}
				}
			}

			// 2.상하좌우만 이동 가능
			for (int i = 0; i < mdr.length; i++) {
				nr = n.row + mdr[i];
				nc = n.col + mdc[i];

				if (nr == 0 && nc == 0) {
					continue;
				}

				if (!isValid(nr, nc, n.k)) {
					continue;
				}

				// DP 갱신을 위해 방문체크 하지 않음
				if (DP[nr][nc][n.k] >= DP[n.row][n.col][n.k] + 1) { // 이동횟수가 작거나 같다면
					DP[nr][nc][n.k] = (DP[n.row][n.col][n.k] == Integer.MAX_VALUE) 
							? 1 : DP[n.row][n.col][n.k] + 1;
					
					if (nr == H - 1 && nc == W - 1) { return; }
					
					visited[nr][nc][n.k] = true;
					queue.add(new Node(nr, nc, n.k)); // count 변수 유지
				}
			}

		}

		return;
	}

	private static boolean isValid(int nr, int nc, int k) {
		return (nr > -1 && nc > -1 && nr < H && nc < W && !visited[nr][nc][k] && board[nr][nc] != 1);
	}
}

class Node {
	int row;
	int col;
	int k; // 말처럼 움직인 횟수

	public Node(int row, int col, int k) {
		this.row = row;
		this.col = col;
		this.k = k;
	}
}

git 링크

https://github.com/jinju9553/23-CodingTest/blob/d7fc616fdbc06fdbf37eaa427959886d27734e52/%EB%B0%B1%EC%A4%80/Gold/1600.%E2%80%85%EB%A7%90%EC%9D%B4%E2%80%85%EB%90%98%EA%B3%A0%ED%94%88%E2%80%85%EC%9B%90%EC%88%AD%EC%9D%B4/%EB%A7%90%EC%9D%B4%E2%80%85%EB%90%98%EA%B3%A0%ED%94%88%E2%80%85%EC%9B%90%EC%88%AD%EC%9D%B4.java

문제 풀이 날짜: 2023.08.29
포스트 작성일: 2023.08.30

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

동적 계획법, 조합론

키워드

백준 온라인 저지 1010번: 다리 놓기 (실버5)

풀이 접근법

• 큰 문제의 해가 작은 문제의 해를 포함하는 형태이므로 점화식을 세워볼 수 있다.
• i번째 사이트가 j번째 사이트를 선택하여 다리를 놓았다면, 그 이전에 i - 1번째 사이트가 세워놓았던 다리가 결정되어 있을 것이다. 이를 DP로 더하여 누적한다.
• 0번 출발지가 0번 도착지를 선택한다면 다리를 1개 세울 수 있다.
  • 0번 출발지가 1번 도착지를 선택해도 다리를 1개 세울 수 있다.
  • …
  • 1번 출발지가 3번 도착지를 선택한다면 그 이전에 0번 출발지는 0, 1, 2번 도착지를 선택한 경우의 수를 가지고 있다.
  • 3번 출발지가 4번 도착지를 선택한다면 그 이전에 2번 출발지가 0, 1, 2, 3 도착지를 선택한 경우의 수를 가지고 있으며, 그 이전의 경우의 수도 모두 포함한다.
  • 따라서 점화식은 DP[n][m] = ∑ DP[n-1][k] (k = 0 ~ j-1)​

코드

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

public class Main {

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

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

		StringBuilder sb = new StringBuilder();
		for (int tc = 0; tc < T; tc++) {

			String[] temp = br.readLine().split(" ");

			int N = Integer.parseInt(temp[0]);
			int M = Integer.parseInt(temp[1]);

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

			for (int i = 0; i < M; i++) {
				DP[0][i] = 1;
			}
			
			for (int i = 1; i < N; i++) {
				for(int j = 0; j < M; j++) {
					if(i > j) { continue; }
					
					for (int k = 0; k < j; k++) {
						DP[i][j] += DP[i - 1][k]; 
					}
				}
			}
			
			int result = 0;
			for(int i = 0; i < M; i++) {
				result += DP[N - 1][i];
			}
			
			sb.append(result).append("\n");
		}

		System.out.println(sb);
	}
}

git 링크

https://github.com/jinju9553/23-CodingTest/blob/41aaeed58066dc701c40e93b194b966da2b74fbc/%EB%B0%B1%EC%A4%80/Silver/1010.%E2%80%85%EB%8B%A4%EB%A6%AC%E2%80%85%EB%86%93%EA%B8%B0/%EB%8B%A4%EB%A6%AC%E2%80%85%EB%86%93%EA%B8%B0.java

문제 풀이 날짜: 2023.08.24
포스트 작성일: 2023.08.26

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

BOJ 15961번: 회전초밥 (골드4)

키워드

투 포인터, 슬라이딩 윈도우

풀이 접근법

• 주어진 그림이 그래프와 유사하지만 그래프로 풀기는 어렵다.
• 투 포인터와 슬라이딩 윈도우를 사용해 풀이한다. k개의 원소를 한꺼번에 확인하면서 옆으로 한 칸씩 민다.
• 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공 ⇒ 결과로 찾은 k개의 초밥 가짓수에 이 가짓수를 보너스로 더할 수 있음. (+1)
• 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다. ⇒ 주어진 레일에 없어도 무관.
• 투 포인터를 이용한 풀이
  • 투 포인터 변수 p와 q는 항상 k(연속해서 먹는 접시 수)만큼 차이난다. p와 q를 1씩 증가시키며 탐색했다가 가장 처음 상태로 되돌아 온다면 탐색을 멈춘다.
  • Set에 현재까지 선택한 접시의 가짓수를 저장한다. Set에 쿠폰번호에 해당하는 접시가 있다면(contains()) 그대로 결과를 취하고, 있지 않으면 쿠폰 접시를 포합한 가짓수를 결과로 저장한다.
• 주의해야 할 반례
  • 문제에서 주어진 예시에서 {7, 9, 7, 30} 이라는 묶음을 확인할 때, 이 다음 탐색에는 첫 번째 접시(7)를 제거하고 마지막 위치에 새 접시(2)를 가져와야 한다.
  • 따라서 다음 탐색의 이상적인 접시 묶음은 {9, 7, 30, 2} 이다.
  • 그런데 Set에서 7을 제거해버리면 Set 안의 모든 7이 삭제되기 때문에 {9, 30, 2}가 되어버린다.
  • 따라서 중복되는 접시 수를 세고 있다가 0이 되는 순간에만 Set에서 제거해주자.

코드

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

public class Main {

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

		String[] temp = br.readLine().split(" ");

		int N = Integer.parseInt(temp[0]); // 벨트에 놓인 접시의 수
		int d = Integer.parseInt(temp[1]); // 초밥의 가짓수
		int k = Integer.parseInt(temp[2]); // 연속해서 먹는 접시 수
		int c = Integer.parseInt(temp[3]); // 쿠폰번호

		int[] dishes = new int[N]; // 벨트 위에 놓인 모든 접시
		int[] selections = new int[d + 1]; //중복 접시 세기, 0은 사용하지 않음
		Set<Integer> set = new HashSet<>(); // 선택된 접시의 가짓수를 모은다.

		for (int i = 0; i < N; i++) {
			int v = Integer.parseInt(br.readLine());
			dishes[i] = v;
		}

		int p = 0;
		int q = p + k - 1;

		for (int i = 0; i <= q; i++) {
			set.add(dishes[i]); // 초기 상태
			selections[dishes[i]]++;
		}

		int initP = p;
		int initQ = q;

		int currMax = -1;
		do {
			currMax = Math.max(set.size(), currMax);

			if (!set.contains(c)) {
				currMax = Math.max(set.size() + 1, currMax);
			}
			
			selections[dishes[p]]--;
			if(selections[dishes[p]] == 0) {
				set.remove(dishes[p]);
			}
			
			if (p + 1 >= N) {
				p = 0;
			} else p++;

			if (q + 1 >= N) {
				q = 0;
			} else q++;
			
			selections[dishes[q]]++;
			set.add(dishes[q]);
		} while (p != initP || q != initQ);
		
		System.out.println(currMax);
	}
}

git 링크

(git 링크 첨부)