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

1. 문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 2. 풀이과정 1. map이라는 2차원 배열에 1은 사과, 2는 뱀으로 표시한다. 또 다른 2차원 배열에는 다음 꼬리를 찾는 데 사용할 방향을 표시한다. 2. 머리는 해당 방향으로 한 칸 전진한다. 3. 사과를 먹으면, 그냥 넘어가고 사과를 먹지 않으면, 꼬리를 제거한다. import java.io.BufferedReader; import java.io.InputStreamReader; imp..

1. 문제 https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 2. 풀이과정 문제분석 2단계에서 이미 설치된 폭탄은 무조건 다음 단계에서 터지게 되어있다. [case1] 초기에 설치된 폭탄은 1초 대기후, 2단계 => 3단계를 거치기 때문에 3초에 터진다. [case2] 2단계에서 새로 설치한 폭탄 => 3=>2(이미 설치된 폭탄으로 취급됨)=>3단계에서 터진다. 구현방법 1. 이미 설치된 폭탄의 위치를 배열에 저장 2. 다음 단계(주어진 문제에서 3단계에 해당)에..

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/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 2. 풀이과정 MST 알고리즘은 kruskal, prim이 있다. 여기서는 간선의 수가 적으므로 kruskal을 사용했다. 처음에는 전체 edge를 입력으로 받아서 오름차순 정렬 후, 최대 & 최소 MST를 찾았다. 하지만, 이 문제에서는 cost가 0, 1 두 가지로 주어지기 때문에 정렬을 하지 않고 오르막길과 내리막길을 따로 모아서 최대로 만들 수..

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..