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

1. 문제 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 2. 풀이 과정 처음에 문제를 이해하는 게 제일 어려웠다. 결국 처음 풀 때는 문제를 완전히 이해하지 못하고 풀어 비효율적인 풀이였지만 통과는 했었다. 헷갈렸던 부분은 두 가지였다. 첫 번째는 컨베이어 벨트의 번호는 컨베이어 벨트가 회전할 때 같이 움직이는 것이고, 올리는 위치 내리는 위치는 그림 속처럼 시작점부터 0번째 N번째 위치를 의미한다. 두 번째는 로봇이 ..

1. 문제 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 2. 풀이과정 1. 중복된 수가 들어오지 않으므로, 1차원 배열에 값이 있는지 여부를 기록한다. 2. 배열의 index는 절댓값이 1_000_000이하이기 때문에, 음수도 가능하므로 (들어온 값) + 1_000_000으로 하여 값을 true로 바꿔준다. 3. 출력할 때, 배열을 처음부터 끝까지 돌면서 true면 (index값) - 1_000_000하여 결과를 출력한다. imp..

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