즐거운사람의블로그

https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net ✔ 문제 조건 행 R 1초부터 2초까지 폭탄을 설치하기 때문에, 2초부터 모든 칸에 폭탄이 있다고 풀어야 한다. (이 부분을 이해 못해서 한참을 못풀었다;;) 1초가 지난 후 (3초부터) 3초 전에 설치된 폭탄이 모두 폭발한다. 폭발하면서 4방향으로 인접한 폭탄들을 폭발시킨다. 3, 4번을 반복한다. ✔ 접근 과정 char형의 2차원 배열을 int형으로 바꾸어 저장한다. 빈칸은 -1로, 초기에 설치된 폭탄은 0초에..

https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 예전에 dfs로 완전탐색 했을 때는 시간초과가 났던 문제인데 dp를 공부한 후 다시 푸니까 풀려서 기분이 좋다^^ ✔ 문제 조건 30개 이하의, N개의 추가 있으며, 각 추들의 무게는 500이하이다. 같은 무게의 추가 여러 개 있을 수 있다. 추의 무게를 담은 배열을 balls[N+1] 라고 한다면, N

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net ✔ 문제 조건 N명의 학생(정점), M개의 단방향 도로(간선)이 있다. 학생들은 모두 X번째 마을까지 최단거리로 갔다가 돌아와야 한다. X번째 마을까지 갔다가 돌아오는 시간이 가장 긴 학생의 소요 시간을 출력한다. ✔ 접근 과정 이 문제는 두가지 거리들을 구해야한다. 1) 각 지점에서 X지점까지의 최단거리 2) X지점에서 각 지점까지의 최단거리 단방향 그래프이기 때문..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 그동안 제일 취약했던 DP문제들을 풀어볼 생각이다.. 이 문제에서는 맨 위층부터 시작해서 아래에 있는 수 중 하나를 택하며 아래층으로 내려올 때 1) 현재 수의 바로 밑에 있는 수 2) 대각선 오른쪽 아래에 있는 수 들 중에서만 택할 수 있다. 즉, arr[i][j]를 택할 수 있는 위치는 1) 바로 위의 수 2) 대각선 왼쪽 위에 있는 수들이다. 1), 2) 의 위치에서 더 큰 합을 가지는 경우를 택하여 arr[i][j]의 수를 더해주면 (i, j)번째의 최적의 합이..

www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net import java.util.*; import java.io.*; // 210424 public class Main_BJ_17472_다리만들기2 { static int N, M; static int[][] map; static StringBuilder sb; static int[][] adjMatrix; static int[] dr = {-1, 0, 1, 0}; static int[] d..

www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net import java.io.*; import java.util.*; // 210416 public class Main_BJ_20057_마법사상어와토네이도 { static int N; static int[][] map; static int out; public static void main(String[] args) throws Exception { //System.setIn(ne..

www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 활성 바이러스가 비활성 바이러스를 지나가면서 활성화 시킨다면, 새롭게 활성화된 바이러스에 대해 어떻게 처리해야 하는지 이해가 안갔는데.. 새롭게 활성화된 바이러스 또한 전파를 시작한다. 그러나 시간을 0초로 되돌릴 수 없기 때문에 방문 배열에는 0으로 표기하더라도 걸리는 시간은 여전히 cur.time +1로 처리하며 큐에 넣어주면 된다. import java.io.*; import java.util.*; // 21042..

www.acmicpc.net/problem/1714317143번: 낚시왕낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.www.acmicpc.net import java.io.*; import java.util.*; // 210423 public class Main_BJ_17143_낚시왕 { static int R, C, M, total; static int[] dr = {-1, 1, 0, 0}; // 상 하 우 좌 static int[] dc = {0, 0, 1, -1}; static Shark[][] map; static class Sha..