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

1. 문제 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 2. 풀이과정 1. 재귀를 사용하여, n자리의 가능한 모든 순열을 구한다. 이때, 중간 값이 소수가 아닌 수는 가지치기로 return한다. 2. 해당 수가 sqrt(해당_수)보다 같거나 작은 값으로 나눠지는지 확인하여, 소수 여부를 판단한다. *에라토스테네스의 체는 최대 크기가 boolean[100_000_000]인 배열이 사용된다. boolean은 하나에 1byte인데 여기..

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