네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/2310 2310번: 어드벤처 게임 입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타 www.acmicpc.net 2. 풀이 과정 자주 풀어왔던 2차원 배열의 dfs가 아니라 다음에 갈 좌표가 주어지는 dfs 문제이다. 백트래킹할 때, 가격은 원래 값을 보장해줘야 하므로 temp라는 변수를 추가로 사용하여 구현하였다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; ..

1. 문제 https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 2. 풀이과정 1. 간선의 개수가 노드 수에 비해 현저히 적으므로, kruskal을 선택했다. 2. cost가 적은 간선부터 탐색하기 위해 PriorityQueue를 사용 import java.io.BufferedReader; import java.io.InputS..

1. 문제 https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 2. 풀이 과정 1. 에라토스테네스의 체를 이용하여 소수를 구한다.2. 소수인 경우에 팰린드롬인지 확인하는데, 숫자를 문자열로 바꿔서 대칭인지 확인하도록 하였다. import java.util.Scanner; public class Main { static int N; static final int MAX = 1_004_000; static bool..

1. 문제 https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 2. 풀이 과정 방법 1. bfs 그래프는 MST로 주어지기 때문에, 인접리스트로 입력을 받았다.구현 방식은 매 query마다 bfs탐색을 하며, 가중치가 k이상인 경우만 더 탐색하도록 한다. 더보기 import java.io.BufferedReader; import java.io.InputStreamReader; import java..

1. 문제 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 2. 풀이 과정 순열로 모든 경우의 수를 구하고, 순열마다 계산해서 최대값을 찾는다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N; static int[] arr, selected; static int resul..

1. 문제 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 2. 풀이 과정 1. Truck을 클래스로 선언한다. 속성은 truck의 무게와 다리를 얼마나 건넜는지에 대한 거리 정보 2가지를 가진다. 2. 도착한 트럭이 N개가 될 때까지, simulation을 반복한다. 3. simulation은 도착한 다음 트럭부터 대기중인 트럭(next)까지 돌면서 distance++을 해서 다리를 한칸씩 건너..

1. 문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 과정 주어진 input이 인접 행렬이며, 간선의 개수가 많을 수도 있기 때문에 인접 행렬을 사용했다. 또한, 모든 정점에서 모든 정점으로의 경로 여부를 묻고 있어서 플로이드 워샬로 문제를 풀었다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static..

1. 문제 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 2. 풀이 과정 1. 시작점부터 중복 허용 즉, 방문 체크 없이 dfs로 탐색해서 5번 이동하는 경로를 찾는다. 2. 완성된 6자리 수는 boolean배열에 해당 수의 index에 해당하는 값을 true로 변경해주고 마지막에 true인 값을 가진 수의 개수를 출력한다. import java.io.BufferedReader; import java..

1. 문제 https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 과정 1. 문자열로 입력을 받아서, 문자 하나씩 읽으면서 배열에 해당 숫자의 개수가 몇 개인지 count한다. 2. 6과 9는 서로 변환이 가능하므로, (arr[6] + arr[9])/2한 수에서 올림을 한 값으로 고려해준다. 3. 0~8까지 탐색하면서 최대값을 찾아 출력한다. (*9는 6에 반영되었으므로 무시한다.) import java.util.Scanner; public class Main { public static void main(String[] args) { S..

1. 문제 https://www.acmicpc.net/problem/14716 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 2. 풀이 과정 8방향 탐색은 dfs로 구현하였으며, 방문 체크는 입력 값을 2로 바꾸어 표시했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, M, map[][]; static int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, ..