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

1. 문제 https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 2. 풀이과정 1. 우선 순위 관계를 boolean 2차원 배열에 저장한다. 이때, 1~N까지인 팀이 있으므로 첫 번째 요소를 찾기위해 제일 첫 번째를 0으로 지정하고 시작했다. 2. 위상 정렬으로 자신의 앞에 아무것도 없는 노드가 다음 순서가 된다. 3. 아직 방문하지 않은 모든 노드의 앞에 누군가가 있다면, 순위를 예측할 수 없는 경우이다. import java.io.Buff..

1. 문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 2. 풀이과정 집의 좌표가 10억이므로, 전체를 둘러보면 시간초과가 발생하므로 이진탐색을 택했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main..

1. 문제 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 2. 풀이과정 방법1. 연산자를 N-1개 고르고, 연산 결과 0이면 StringBuilder로 합치기 더보기 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static int N; static StringBuilder sb; static char operation[] = {' ', '+','-'}, selected[]; public s..

1. 문제 https://www.acmicpc.net/problem/3671 3671번: 산업 스파이의 편지 각 테스트 케이스에 대해 종이조각을 적절히 배치해서 만들 수 있는 서로 다른 소수의 개수를 출력한다. 이때, 모든 종이 조각을 사용하지 않아도 된다. (7과 1이 있을 때, 만들 수 있는 소수는 7, www.acmicpc.net 2. 풀이 과정 1. 주어지는 input의 숫자 하나하나를 int[]로 변환한다. 2. 순열을 이용하여 모든 경우의 수를 탐색한다. 3. 집합으로 중복된 값은 소수 판단 여부에서 제외한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; import java...

1. 문제 https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 2. 풀이 과정 1. dfs로 모든 경로 탐색을 한다. 2. 도착점에서 해당 경로가 K면 result+=1 아니면, 해당 경로는 그만 탐색하도록 한다. 또한, 아직 도착점이 오지 않았지만 경로가 이미 K이상이면 더 이상 탐색할 필요가 없으므로 탐색을 종료한다. import java.io.BufferedReader; import java.io.Inp..

1. 문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 2. 풀이 과정 1. 4방향 탐색하면서 빙산이면 dfs탐색하고, 빙산이 아니면 cnt+1을 한다. 2. 한 번 dfs탐색이 끝났는데, 또 dfs탐색할 곳이 남았다면 분리되었다는 것으로 판단하고 종료한다. 3. dfs 탐색이 끝나고 2중 for문으로 전체를 돌면서 주변 0의 개수만큼 숫자를 빼준다. import java.io.BufferedReader; import java.io.I..

1. 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 2. 풀이과정 MST 문제로 Kruskal이나 Prim으로 접근할 수 있다. 노드 수가 1000개, 간선 수가 최대 100,000로 N(N-1)보다 10배 적은 수이다. 따라서 여기서는 kruskal을 활용해서 풀었다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { s..

1. 문제 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 2. 풀이 과정 1. 시작점에서 출발해서 bfs로 탐색한다. 2. PriorityQueue를 사용해서 변환 횟수가 적은 것부터 탐색하면, 해당 블럭마다 변환횟수가 가장 적은 경로로 탐색하게 되므로 도착점에 오는 순간 바로 종료한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Prior..

1. 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 풀이 과정 - bfs import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static void ma..

1. 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2. 풀이 과정 1. (0, 0)에서 시작해서 치즈 있는 곳을 만나면, 치즈 있는 곳에 +1을 해준다. 2. 치즈가 있는 곳이 3이 되는 순간 2면이 외부와 닿아있다는 의미이므로 다음 탐색할 노드에 추가해준다. 3. next = 다음 탐색할 노드들의 모음으로 각 노드마다 dfs로 치즈 있는 곳을 만나면, 치즈 있는 곳에 +1을 하고 2단계를 반복한다. import java...