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

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

1. 문제 https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 과정 1. 문자열로 입력을 받아서, 문자 하나씩 읽으면서 배열에 해당 숫자의 개수가 몇 개인지 count한다. 2. 6과 9는 서로 변환이 가능하므로, (arr[6] + arr[9])/2한 수에서 올림을 한 값으로 고려해준다. 3. 0~8까지 탐색하면서 최대값을 찾아 출력한다. (*9는 6에 반영되었으므로 무시한다.) import java.util.Scanner; public class Main { public static void main(String[] args) { S..

1. 문제 https://www.acmicpc.net/problem/14716 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 2. 풀이 과정 8방향 탐색은 dfs로 구현하였으며, 방문 체크는 입력 값을 2로 바꾸어 표시했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, M, map[][]; static int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, ..

1. 문제 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 2. 풀이 과정 dfs로 같은 팀끼리 인접한 수를 구하는데, 방문체크는 W, B => . 으로 변경하여 확인하였다. import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static int N, M, result, dx[] = {-1, 0, 1, 0}, dy[] =..

1. 문제 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 2. 풀이과정 문제 제목부터 플로이드 문제라고 알려주고 있었다. 플로이드 워샬로 풀면서, 이 문제에 주의할 점은 두 가지가 있다. 1. 같은 경로가 두 번 들어올 수 있어서, 입력받을 때 최솟값인지 확인하고 저장해줘야 한다. 2. 경로가 없는 경우는 0으로 출력해야 한다. 따라서 INF를 (도시의 개수)*(최대비용) +1 =10_000_001로 두었다. import java.io.Buf..

1. 문제 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 2. 풀이과정 K개 중에 6개를 뽑는 조합 문제이다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int arr[], k; static StringBuilder sb; public static vo..

1. 문제 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 2. 풀이과정 1. 울타리가 아니면 dfs 탐색 시작 2. 탐색하면서 늑대와 양의 수를 센다. 3. 탐색이 끝나면 늑대와 양의 수를 비교해서 결과에 반영한다. import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static int N, M, dx[] = {-1, 0, 1, 0..

1. 문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 2. 풀이과정 백트래킹 문제로, 각 감시카메라마다 가능한 감시 구역을 모두 탐색하며 결과값을 찾는다. N, M의 범위가 작기 때문에 전체탐색을 해도 시간 초과가 나지 않는다. 1. 전체 구역, 즉 2차원 배열을 재귀함수 simulation으로 전체 탐색을 한다. 2. 이때 해당 구역에 감시카메라가 있다면, 각 번호별로 탐색할 수 있는 구역을 탐색하고 재귀를 진행한다. 3. 감..