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

1. 문제 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 2. 풀이 과정 처음에 어떤 알고리즘을 쓰지 등 복잡하게 생각하지 않고, 문제만 생각하는 습관을 길러야 될 것 같다. 한 column에서 최대 채울 수 있는 물의 양을 구하는 방법은 아래와 같다. 1. 해당 column 왼쪽과 오른쪽 각각에서 블럭의 최대 높이를 찾기 2. 둘 중 작은 값만큼 채울 수 있음 구현방법 해당 column마다 자신의 왼쪽에 있는 블럭 중 최대..

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