해당 문제는 시뮬레이션 문제로 단계별로 수행하는 함수를 이용하여 풀 수 있는 문제입니다.

17144. 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

인접한 네 방향으로 모두 확산이 일어난다.

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력(Input)

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력(Output)

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

1. 문제 풀이

이 문제를 풀때에 생각해야할 제일 중요한 핵심은 두 가지 입니다.

1. 확산에서 각 현 위치의 값만 고려해서 겹치는 칸은 더해진다.
2. 공기청정시 돌아가는 배열 돌리기.

1번은 확산 예시 3번 그림을 보았을때

• (0, 1)에 30이 세 방향으로 확산되었기 때문에 30 - ((30/5)*3) = 12라는 남는 부분과 확산되어 오는 두 방향에서의 계산식 11 / 5 = 2, 7 / 5 = 1 즉, 12 + 2 + 1 = 15
• (0, 2)에 7이 두 방향으로 확산되었기 때문에 7 - ((7/5)*2) = 5라는 남는 부분과 확산되어 오는 한 방향에서의 계산식 30/5 = 6 즉, 5 + 6 = 11

따라서 한 칸씩 이동하면서 계산을 해주면 됩니다.

2번은 배열돌리기 입니다. 배열은 사각형 모양으로 끝을 만나기 전까지 INDEX를 계속 반복하여 증가/감소를 하다가 끝이라는 경계를 만나면 각 인덱스의 증가/감소 플래그를 바꿔주면 됩니다.

• 인덱스는 i,j라고 합니다. (여기서 끝은 배열 구분선 직전까지를 의미합니다. 즉, 인덱스의 범위)
• 처음 공기청정기의 위치에 따라서 반으로 나누고 i,j의 범위를 정해줍니다. (예시는 아래쪽 기준)
• 처음에는 i가 증가하는 방향으로 가다가 끝을 만나면 멈추고 j를 증가시켜 줍니다.
• j가 증가하는 방향으로 가다가 끝을 만나면 멈추고 i를 감소시켜 줍니다.
• i를 감소시켜주다가 공기청정기를 만나면 종료합니다.

이렇게 순차적으로 배열돌리기를 하면서 다음에 있는 값을 저장하고, 해당 위치로 이동해 넣어주고를 반복해줍니다.

이것을 코드로 표현하겠습니다.

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


public class Bye_Microcum {
	// (6 <= R,C <= 50, 1<= T <= 1000) (-1 <= Arc <= 1000)
	// 공기청정기 위치는 -1, -1은 위아래 붙어있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.
	static int R, C, T, result;
	static int[][] A, B;
	static int[][] idx = {
			{-1, 0, 1, 0},
			{0, -1, 0, 1}
	};
	static int upR, upC, downR, downC;
	
	static void diffusion() {
		B = new int[R][C];
		
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if(A[i][j] == -1) {
					B[i][j] = -1;
					continue;
				}
				int cnt = 0;
				if(A[i][j] != 0) {					
					for (int k = 0; k < 4; k++) {
						int nxR = i + idx[0][k];
						int nxC = j + idx[1][k];
						if(nxR < 0 || nxC < 0 || nxR >= R || nxC >= C || A[nxR][nxC] == -1) {
							continue;
						} else {
							B[nxR][nxC] += A[i][j] / 5;
							cnt++;
						}
					}
					B[i][j] += A[i][j] - ((A[i][j]/5)*cnt);
				}
			}
		}
		
		// 배열 복사
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				A[i][j] = B[i][j];
			}
		}
	}
	
	static void air_cleanning() {
		int temp, nextTemp, dir;
		
		int[][] up = {
				{0, -1, 0, 1},
				{1, 0, -1, 0},
		};
		int i = upR, j = upC + 1; dir = 0;
		nextTemp = A[i][j];
		A[i][j] = 0;
		while(true) {
			temp = nextTemp;
			int nR = i + up[0][dir];
			int nC = j + up[1][dir];
			if(nR < 0 || R <= nR || nC < 0 || C <= nC) {
				dir++;
				nR = i + up[0][dir];
				nC = j + up[1][dir];
			} else if(A[nR][nC] == -1) break;
			nextTemp = A[nR][nC];
			A[nR][nC] = temp;
			i = nR; j = nC;
		}
		
		int[][] down = {
				{0, 1, 0, -1},
				{1, 0, -1, 0},
		};
		i = downR; j = downC + 1; dir = 0;
		nextTemp = A[i][j];
		A[i][j] = 0;
		while(true) {
			temp = nextTemp;
			int nR = i + down[0][dir];
			int nC = j + down[1][dir];
			if(nR < 0 || R <= nR || nC < 0 || C <= nC) {
				dir++;
				nR = i + down[0][dir];
				nC = j + down[1][dir];
			} else if(A[nR][nC] == -1) break;
			nextTemp = A[nR][nC];
			A[nR][nC] = temp;
			i = nR; j = nC;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		
		A = new int[R][C];
		boolean air_condition = false;
		for (int i = 0; i < R; i++) {
			if(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
				if(A[i][j] == -1 && !air_condition) {
					upR = i; upC = j;
					downR = i + 1; downC = j;
					air_condition = true;
				}
			}
			
		}
		
		for (int i = 0; i < T; i++) {
			diffusion();
			air_cleanning();
		}
		
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if(A[i][j] == -1) continue;
				result += A[i][j];
			}
		}
		
		System.out.println(result);
	}
}

해당 문제는 시뮬레이션 문제로 단계별로 수행하는 함수를 이용하여 풀 수 있는 문제입니다.

14503. 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

로봇 청소기는 다음과 같이 작동한다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

입력(Input)

첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.

로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.

출력(Output)

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

1. 문제 풀이

이 문제를 풀때에 생각해야 할 것은 두 가지 입니다.

1. 최초의 자리도 청소
2. 바라보고 있는 방향에 따라서 왼쪽의 좌표를 설정하는 것

최초에 자리를 청소한다고 하고 map에서 현 자리를 청소 한걸로 표시하고 스타트 합니다.

그리고 바라보고 있는 방향 왼쪽 좌표를 바라보기 때문에 배열에 현재 바라보고 있는 방향을 인덱스로 왼쪽을 보는 값을 고정 시켜줍니다. 저는

// 북 - (0,-1), 동 - (-1,0), 남 - (0,1), 서 - (1,0)
static int[][] left = { {0, -1, 0, 1}, {-1, 0, 1, 0}, };

으로 고정시켜서 사용하였습니다.

• 현재 북쪽을 바라보고 있고, 왼쪽 방향을 탐색하려 합니다.
• left[0][] 에 있는 값을 현재 위치에서 더해주고, 청소가 가능하면 청소를하고 해당 방향으로 변경
• 청소가 불가능하면 해당 방향으로 회전하여 다시 진행
• 네 방향 모두 불가한 것을 체크하기 위해 count 변수를 두어 확인해 주고 네 방향 전부 불가능 하면 현재 바라보고 있는 방향에서 뒤로 한 칸 후진 합니다.
• 만약 후진도 못하면 종료합니다.

이것을 코드로 표현하겠습니다.

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


public class Robot_Vaccumcleaner {
	// 3 <= N, M <= 50 || 0 - empty, 1 - wall
	// d : 0 - North, 1 - East, 2 - South, 3 - West
	// 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색
	// 로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.
	static int N, M, r, c, d;
	static int clean;
	static int[][] map;
	// 바라보고 있는 방향에 따라서 탐색하는 왼쪽의 좌표가 다르다.
	// 북 - (0,-1), 동 - (-1,0), 남 - (0,1), 서 - (1,0)
	static int[][] left = {
			{0, -1, 0, 1},
			{-1, 0, 1, 0},
	};
	
	static void cleanning() {
		int cnt = 0;
		while(true) {
			int nxR = r + left[0][d];
			int nxC = c + left[1][d];
			if(nxR < 0 || N <= nxR || nxC < 0 || M <= nxC || map[nxR][nxC] == -1 || map[nxR][nxC] == 1) {	// 왼쪽에 청소 할 공간이 없다면, 그 위치로 회전.
				if(cnt >= 4) {	// 네 방향 모두 청소가 되어 있거나 벽인경우 방향 그대로 뒤로 후진
					switch(d) {
						case 0: nxR = r + 1; nxC = c; 	  break;
						case 1: nxR = r; 	 nxC = c - 1; break;
						case 2: nxR = r - 1; nxC = c; 	  break;
						case 3: nxR = r; 	 nxC = c + 1; break;
					}
					if(map[nxR][nxC] == 1) {	// 네 방향 모두 청소가 됭 있고, 뒤가 벽인 경우 종료.
						break;
					}
					r = nxR; c = nxC;
					cnt = 0;
				} else {
					d -= 1;
					if(d < 0) d = 3;
					cnt++;
				}
			} else if(map[nxR][nxC] == 0) {	// 왼쪽 방향에 청소 공간이 존재한다면,
				d -= 1;
				if(d < 0) d = 3;
				map[nxR][nxC] = -1;
				clean++;
				cnt = 0;
				r = nxR; c = nxC;
			}
		}
	}
	
	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());
		map = new int[N][M];
		st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		for (int i = 0; i < N; i++) {
			if(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		clean = 1; map[r][c] = -1;
		cleanning();
		
		System.out.println(clean);
	}
}

해당 문제는 완전탐색으로 풀 수 있는 문제다. 벽을 세우는 경우를 전부 해보고 안전 영역의 최대 크기를 구하면 된다.

14502. 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력 (Input)

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력(Output)

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

1. 문제풀이

이 문제를 풀때에 생각해야할 부분은 두 가지 입니다.

1. 이 차원 배열로 이루어진 map에 임의의 벽 3개를 어떤 방식으로 세운다고 가정할 것인가?
2. 확산시 방문 체크와 어떻게 전체에 바이러스를 퍼졌다고 할까?

1번은 완전 탐색 DFS를 통해서 세우고 해제하고를 하며 재귀를 돌아 최종적으로 벽을 3개 세웠을 때, 확산을 실행하여 남은 안전 영역을 구하면 됩니다.

2번은 확산에 대한 좌표를 큐에 담고, 큐에서 바이러스가 있는 공간을 하나씩 빼서 상, 하, 좌, 우로 바이러스가 퍼질 수 있는 공간이면 맵에 기록하고 큐에 새로운 바이러스를 넣어주며 큐에 더이상 확산할 수 있는 바이러스가 없을때까지 반복하여 해결합니다.

이것을 코드로 표현하겠습니다.

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

public class Institute {
	// 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.
	// 바이러스는 상, 하, 좌, 우로 퍼져 나간다.
	// 0은 빈칸, 1은 벽, 2는 바이러스
	static int N, M, safty, listSize;
	static ArrayList<Block> list, virusList;
	static Queue<Block> virus;
	static int[][] map;
	static boolean[][] visited;
	static int[][] dif = {
			{0, 1, -1, 0},
			{1, 0, 0, -1},
	};
	
	static void virus(int cnt, int idx) {
		if(cnt == 3) {
			visited = new boolean[N][M];
			diffusion();
			int max = searchSafy();
			if(max > safty) safty = max;
			return;
		}
		
		if(listSize <= idx) return;
		
		Block tmp = list.get(idx);
		map[tmp.x][tmp.y] = 1;
		virus(cnt + 1, idx + 1);
		map[tmp.x][tmp.y] = 0;
		virus(cnt, idx + 1);
	}
	
	static void diffusion() {
		virus.clear();
		
		for (int i = 0; i < virusList.size(); i++) {
			virus.add(virusList.get(i));
		}
		
		while(!virus.isEmpty()) {
			Block tmp = virus.poll();
			visited[tmp.x][tmp.y] = true;
			for (int i = 0; i < 4; i++) {
				int nx = tmp.x + dif[0][i];
				int ny = tmp.y + dif[1][i];
				if(0 <= nx && nx < N && 0 <= ny && ny < M && map[nx][ny] == 0 && !visited[nx][ny]) {
					visited[nx][ny] = true;
					virus.add(new Block(nx, ny));
				}
			}
		}
	}
	
	static int searchSafy() {
		int area = 0;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(map[i][j] == 0 && !visited[i][j]) area++;
			}
		}
		
		return area;
	}
	
	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());
		map = new int[N][M];
		list = new ArrayList<>();
		virusList = new ArrayList<>();
		virus = new LinkedList<Block>();
		for (int i = 0; i < N; i++) {
			if(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 0) {
					list.add(new Block(i, j));
					listSize++;
				} else if(map[i][j] == 2) virusList.add(new Block(i, j));
			}
		}
		
		safty = 0;
		virus(0, 0);
		
		System.out.println(safty);
	}
	
	public static class Block {
		int x, y;
		public Block(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

해당 문제는 DP(Dynamic Programing) 또는 완전탐색으로 풀 수 있는 문제입니다.

우선 문제를 DP를 이용해서 풀어보고, 그 다음 완전탐색을 이용해서 풀어 보았습니다.

14051. 퇴사

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력(Input)

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력(Output)

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

1. DP로 접근

 해당 문제는 첫째날–>마지막날로 접근하는 것보다, 마지막날–>첫째날로 접근하는 것이 더 쉽습니다.

7일에 잡혀있는 일은 2일이 걸리기 때문에 아무리 금액이 높더라도 진행할 수 없습니다.

6일에도 4일이 걸리기 때문에 N+1 즉, 7일이 넘어가기 때문에 진행할 수 없습니다.

5일에는 2일이 걸리는 일이 있습니다. 5~6일에 일을 하고 얻는 15의 수익이 얻을 수 있는 최대 수익입니다.

4일째에는 1일짜리 일을 추가로 하고, 5일까지의 일에 더해주는 것이 최대 수익이 됩니다. 즉, 20 + 15 = 35

3일째에도 1일짜리 일을 추가로 하고, 4일까지의 일에 더해주는 것이 최대 수익이 됩니다. 10 + 20 + 15 = 45

2일째에는 5일이 걸리는 일이 있습니다. 5일을 했을때 최대 이익과 위에서 했던 일중에서 비교를 해봐야 합니다.

2~6일까지 일을 해서 얻는 수익은 20입니다.

이것은 3~6까지 세가지 일을 해서 얻는 수익 45와 비교하면 낮습니다. 그러므로 2일째 일은 하지 않습니다.

1일째에도 마찬가지로 3일이 걸리는 일이 있습니다.

1~3일을 일을 하면 10의 수익을 얻을 수 있습니다.

이것은 3일째에 일을 하는 10의 수익과 같습니다. 그러므로 1일째에 일을 선택하던지 3일째의 일을 선택하던지 하면 최대 수익을 얻을 수 있습니다.

이러한 조건에서 위와 같이 최대 수익은 45가 나올 수 있습니다.

이것을 코드로 표현하겠습니다.

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

/**
 * 14501. 퇴사
 * @author gahusb
 * Input : N - 퇴사전까지 남은 기간, Ti - 상담을 완료하는데 걸리는 기간, Pi - 상담을 했을 때 받을 수 있는 금액
 * Output : 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익
 *
 */
public class Resignation {
	static int[] t, p, dp;
	
	static void calcMaxIncome(int dDay) {
		int next;
		
		for (int i = dDay; i > 0; i--) {
	        next = i + t[i];
	        if (next > dDay + 1) {
	            dp[i] = dp[i + 1];
	        } else {
	            dp[i] = dp[i + 1] > dp[next] + p[i] ? dp[i + 1] : dp[next] + p[i];
	        }
	    }
		
		System.out.println(dp[1]);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		t = new int[N+2];
		p = new int[N+2];
		dp = new int[N+2];
		for (int i = 1; i <= N; i++) {
			if (!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
			t[i] = Integer.parseInt(st.nextToken());
			p[i] = Integer.parseInt(st.nextToken());
		}
		
		calcMaxIncome(N);
	}
}

2. 완전탐색

-- 완전 탐색의 방법은 나중에 추후 업데이트 –

이것을 코드로 표현하겠습니다.

public class Resignation {
	static int[] t, p;
	static int N, income;
	
	static void calcMaxIncome(int day, int cost) {
		if(day > N) {
			return;
		}
		
		income = income > cost ? income : cost;
		
		for (int i = day; i < N; i++) {
			calcMaxIncome(i + t[i], cost + p[i]);
		}
	}
	
	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());
		t = new int[N];
		p = new int[N];
		for (int i = 0; i < N; i++) {
			if (!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
			t[i] = Integer.parseInt(st.nextToken());
			p[i] = Integer.parseInt(st.nextToken());
		}
		
		calcMaxIncome(0, 0);
		System.out.println(income);
	}
}

Study-Algorithms-test

08 Mar 2022 in Dev. Log on Algorithms

깃 블로그를 만들면서 작성해보는 테스트 Post

알고리즘을 공부하고 기록하는 페이지를 모아 놓는다.

작성되는 글

이 디렉토리에는 알고리즘에 대해서 공부하고 내용을 정리하면서 내가 이해한 내용을 작성하는 저장소이다.

지금까지는 머리속으로 이해하고 그것을 활용하는 방식으로 공부를 했지만 성과가 항상 좋지만은 않았다.

그래서 내가 공부하고 이해한 내용을 바탕으로 글로 작성하면서 다시 한 번 떠올리고, 작성하면서 생각의 오류를 수정하고, 남에게 보여지는 글이기 때문에 정확히 알아야만 할 수 있다고 생각이 든다.

이 공간을 가득 채울 수 있도록 다시 한 번 다짐해 본다!

What’s New in Hydejack 9.1?

13 Feb 2021 in Example

Version 9.1 provides minor design changes, new features, and closes multiple issues.

What’s New in Hydejack 9.1?

• Stripe-ified Design
• Inverted Sidebars
• Code Block Headers
• Resume Download Buttons
• SERP Breadcrumbs
• Last Modified At
• Clap Button Preview
• Credits

Stripe-ified Design

Most elements now have rounded borders, making the design look more modern (dare I say “Stripe-ified”) than ever before.

The goal of Hydejack was always to provide a theme that looks “designed” combined the amenities of a typical Jekyll theme for coders. This is an important step in maintaining this goal.

At the same time, I’m introducing nerdy elements like breadcrumbs, that are almost ornamental in nature. You wouldn’t find these on other Stripe-like designs, but I think they are appealing to developer types like myself. Like most additions to Hydejack, they can be disabled via configuration.

Inverted Sidebars

The colors on the sidebar can now be inverted to allow brighter sidebar images. This can be enabled per-page in the fort matter:

invert_sidebar: true

Code Block Headers

Code blocks can now have headers:

// file: 'hello-world.js'
console.log('Hello World!');

Headers are added by making the first line a comment of the form (file|title): ['"].*['"], e.g.:

~~~js
// file: 'hello-world.js'
console.log('Hello World!');
~~~

Code blocks with and without headers now also come with a copy button. In the case of header-less code blocks, the button only shows on hover to prevent potential overlap.

Resume Download Buttons

Resumes can now have download buttons:

Resumes can now have download buttons.

The documentation has been updated with a chapter on how to configure the buttons.

SERP Breadcrumbs

Added breadcrumbs above page title:

Bread crumbs are now shown above each page title.

Note that this requires a directory-like URL structure on your entire site, otherwise the intermediate links will point to nonexisting sites.

On a side note, Hydejack now has built-in tooltips for abbreviations like SERP (activated via tap/click). See Example Content on how to add them to your content.

Last Modified At

Blog posts can now have a “last modified at” date in the sub title row.

Note that this depends on the last_modified_at property of the page, which must be either set manually in the frontmatter (not recommended), or via a plugin like jekyll-last-modified-at. Note that the later is not available when building on GitHub Pages and can increase build times.

Clap Button Preview

I’ve been trying something new with getclaps.app, a feedback and analytics tool for personal sites like those powered by Hydejack.

It is a separate product from Hydejack and not enabled by default. Because it depends on a backend component, it requires a monthly fee. If enabled, it is placed below posts and pages where the dingbat character (❖) used to be.

I can’t claim that this product is fully baked (feedback welcome), but I’ve been using it on my personal site and here for the last couple of months with no issues. For more, see the dedicated website.

There are many more changes and bugfixes in 9.1. See the CHANGELOG for details.

Credits

Photo by JJ Ying on Unsplash

Introducing Hydejack 9

03 Jul 2020 in Example

Version 9 is the most complete version of Hydejack yet. Modernized design, big headlines, and big new features.

Version 9 is the most complete version of Hydejack yet.

Modernized design, big headlines, big new features: Built-In Search, Sticky Table of Contents, and Auto-Hiding Navbar. That and more is Hydejack 9.

• Linking in Style
• Ready for the Big Screen
• What’s in the Cards?
• Built-In Search
• Auto-Hiding Navbar
• Sticky Table of Contents
• …and much more
• Even More to Come
• Get It Now

Linking in Style

Ever since the introduction of Dark Mode, link styles have been a bit of an issue. Specifically, finding an accent color that worked on both light and dark backgrounds was the problem. With Hydejack 9, the link style has been revamped so that legibility is no longer tied to the choice of accent_color, giving you much more freedom in creating a unique design flavor for your site.

Ready for the Big Screen

The theme on which Hydejack is based was designed for a different era of the web. Hydejack has inherited many of its limitations, but over time I’ve made adjustments, such as centering the content column for better reading ergonomics.

With version 9, Hydejack takes full advantage of large displays. Whether it’s design indulgences such as oversized headlines, or quality of life improvements such as a floating table of contents, Hydejack now finds use for all that extra screen real estate¹.

What’s in the Cards?

Hydejack 9 now lets you use content cards for both projects and posts. The cards have been redesigned with a new hover style and drop shadows and they retain their unique transition-to-next-page animations, which now also work on the blog layout. The new grid layout lets you do that.

Good images are key to making the most out of content cards. For that reason, a chapter on images has been added to the documentation.

Built-In Search

Hydejack now has Built-In Search. It even works offline. I’ve been prototyping many approaches and eventually settled on a fully client-side, off-the-main thread solution that perfectly fits the use case of personal sites and shows surprisingly good results².

The new search UI is custom made for Hydejack and shows beautiful previews of your posts and pages, right on top of your regular content.

Together with the Auto-Hiding Navbar, your entire content library is now only a couple of keystrokes away.

Auto-Hiding Navbar

A navbar that’s there when you need it, and disappears when you don’t. Simple as that.

Sticky Table of Contents

Already a staple on so many sites on the web, this pattern is now also available in Hydejack. What’s unique about it is that it simply picks up the table of contents already created by kramdown’s {:toc} tag and transparently upgrades it to a fully dynamic version.

…and much more

Other noteworthy changes include:

• Support for Jekyll 4
• Choice between MathJax and KaTeX for math rendering
• Use of jekyll-include-cache for drastically improved page building speeds
• New variables configuration file — adjust content width, sidebar width, font size, etc…
• …and the option to disable grouping projects by year.

Read the the CHANGELOG for the full scope of features and improvements made in Hydejack 9. Maybe just glance at it to confirm that it is indeed a pretty long list.

Even More to Come

New features for 9.1 are already lined up. Code block headers and code line highlights for even better technical blogging, as well as download buttons on the resume page for PDF, vCard, and Resume JSON are just around the corner.

Get It Now

The Free Version of Hydejack is now availabe on RubyGems and for the first time also on GitHub Packages. The source code is available on GitHub as always.

The PRO Version is scheduled to release on July 7th on Gumroad. Pre-Orders are open now:

Example Content III

01 Jun 2018 in Example

A page showing Hydejack-specific markdown content.

Hydejack offers a few additional features to markup your markdown. Don’t worry, these are merely CSS classes added with kramdown’s {:...} syntax, so that your content remains compatible with other Jekyll themes.

Large Tables

Code blocks

// Example can be run directly in your JavaScript console

// Create a function that takes two arguments and returns the sum of those
// arguments
var adder = new Function("a", "b", "return a + b");

// Call the function
adder(2, 6);
// > 8

Math

Lorem ipsum \(f(x) = x^2\). \[\begin{aligned} \phi(x,y) &= \phi \left(\sum_{i=1}^n x_ie_i, \sum_{j=1}^n y_je_j \right) \\[2em] &= \sum_{i=1}^n \sum_{j=1}^n x_i y_j \phi(e_i, e_j) \\[2em] &= (x_1, \ldots, x_n) \left(\begin{array}{ccc} \phi(e_1, e_1) & \cdots & \phi(e_1, e_n) \\ \vdots & \ddots & \vdots \\ \phi(e_n, e_1) & \cdots & \phi(e_n, e_n) \end{array}\right) \left(\begin{array}{c} y_1 \\ \vdots \\ y_n \end{array}\right) \end{aligned}\]

Message boxes

NOTE: You can add a message box.

Large text

You can add large text.

Large images

Captions to images

A caption to an image.

Large quotes

You can make a quote “pop out”.

Faded text

I’m faded, faded, faded.

Example Content II

23 Nov 2017 in Example

A page showing how regular markdown content is styled in Hydejack.

There should be whitespace between paragraphs. We recommend including a README, or a file with information about your project.

There should be whitespace between paragraphs.

Text can be bold, italic, or strikethrough.

Link to another page.

• Header 2
  • Header 3
    • Header 4
      • Header 5
        • Header 6
  • There’s a horizontal rule below this.
  • Here is an unordered list:
  • And an ordered list:
  • And a nested list:
  • Small image
  • Large image
  • Definition lists

Header 2

This is a normal paragraph following a header. GitHub is a code hosting platform for version control and collaboration. It lets you and others work together on projects from anywhere.

Header 3

This is a blockquote following a header.

When something is important enough, you do it even if the odds are not in your favor.

// Javascript code with syntax highlighting.
var fun = function lang(l) {
  dateformat.i18n = require('./lang/' + l)
  return true;
}

# Ruby code with syntax highlighting
GitHubPages::Dependencies.gems.each do |gem, version|
  s.add_dependency(gem, "= #{version}")
end

Header 4

• This is an unordered list following a header.
• This is an unordered list following a header.
• This is an unordered list following a header.

Header 5

1. This is an ordered list following a header.
2. This is an ordered list following a header.
3. This is an ordered list following a header.

Header 6

There’s a horizontal rule below this.

Here is an unordered list:

• Item foo
• Item bar
• Item baz
• Item zip

And an ordered list:

1. Item one
2. Item two
3. Item three
4. Item four

And a nested list:

• level 1 item
  • level 2 item
  • level 2 item
    • level 3 item
    • level 3 item
• level 1 item
  • level 2 item
  • level 2 item
  • level 2 item
• level 1 item
  • level 2 item
  • level 2 item
• level 1 item

Small image

Large image

Definition lists

Name

Godzilla

Born

1952

Birthplace

Japan

Color

Green

Long, single-line code blocks should not wrap. They should horizontally scroll if they are too long. This line should be long enough to demonstrate this. Or is it?

The final element.

Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Aenean eu leo quam. Pellentesque ornare sem lacinia quam venenatis vestibulum. Sed posuere consectetur est at lobortis. Cras mattis consectetur purus sit amet fermentum.

Curabitur blandit tempus porttitor. Nullam quis risus eget urna mollis ornare vel eu leo. Nullam id dolor id nibh ultricies vehicula ut id elit.

Etiam porta sem malesuada magna mollis euismod. Cras mattis consectetur purus sit amet fermentum. Aenean lacinia bibendum nulla sed consectetur.

Inline HTML elements

HTML defines a long list of available inline tags, a complete list of which can be found on the Mozilla Developer Network.

• To bold text, use **To bold text**.
• To italicize text, use *To italicize text*.
• Abbreviations, like HTML should be defined like this *[HTML]: HyperText Markup Language.
• Citations, like — Mark otto, should use <cite>.
• Deleted text should use ~~deleted~~ and inserted text should use <ins>.
• Superscript ^text uses <sup> and subscript _text uses <sub>.

Most of these elements are styled by browsers with few modifications on our part.

Heading 2

Vivamus sagittis lacus vel augue rutrum faucibus dolor auctor. Duis mollis, est non commodo luctus, nisi erat porttitor ligula, eget lacinia odio sem nec elit. Morbi leo risus, porta ac consectetur ac, vestibulum at eros.

Heading 3

Vivamus sagittis lacus vel augue rutrum faucibus dolor auctor.

Heading 4

Vivamus sagittis lacus vel augue rutrum faucibus dolor auctor.

Heading 5

Vivamus sagittis lacus vel augue rutrum faucibus dolor auctor.

Heading 6

Vivamus sagittis lacus vel augue rutrum faucibus dolor auctor.

Code

Cum sociis natoque penatibus et magnis dis code element montes, nascetur ridiculus mus.

// Example can be run directly in your JavaScript console

// Create a function that takes two arguments and returns the sum of those
// arguments
var adder = new Function("a", "b", "return a + b");

// Call the function
adder(2, 6);
// > 8

Lists

Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Aenean lacinia bibendum nulla sed consectetur. Etiam porta sem malesuada magna mollis euismod. Fusce dapibus, tellus ac cursus commodo, tortor mauris condimentum nibh, ut fermentum massa justo sit amet risus.

• Praesent commodo cursus magna, vel scelerisque nisl consectetur et.
• Donec id elit non mi porta gravida at eget metus.
• Nulla vitae elit libero, a pharetra augue.

Donec ullamcorper nulla non metus auctor fringilla. Nulla vitae elit libero, a pharetra augue.

1. Vestibulum id ligula porta felis euismod semper.
2. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus.
3. Maecenas sed diam eget risus varius blandit sit amet non magna.

Cras mattis consectetur purus sit amet fermentum. Sed posuere consectetur est at lobortis.

HyperText Markup Language (HTML)

The language used to describe and define the content of a Web page

Cascading Style Sheets (CSS)

Used to describe the appearance of Web content

JavaScript (JS)

The programming language used to build advanced Web sites and applications

Integer posuere erat a ante venenatis dapibus posuere velit aliquet. Morbi leo risus, porta ac consectetur ac, vestibulum at eros. Nullam quis risus eget urna mollis ornare vel eu leo.

Images

Quisque consequat sapien eget quam rhoncus, sit amet laoreet diam tempus. Aliquam aliquam metus erat, a pulvinar turpis suscipit at.

Tables

Aenean lacinia bibendum nulla sed consectetur. Lorem ipsum dolor sit amet, consectetur adipiscing elit.

Nullam id dolor id nibh ultricies vehicula ut id elit. Sed posuere consectetur est at lobortis. Nullam quis risus eget urna mollis ornare vel eu leo.