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

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

1. 문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 2. 풀이 과정 1. dfs 탐색으로 해당 구역과 어느 구역이 연합을 맺었는지 구한다. 이때, 연합을 맺은 구역의 좌표와 인구 수의 합을 저장해둔다. 2. 연합 하나를 구할 때마다, 각 구역의 인구수를 (연합의 인구합)/(연합 구역 수)로 업데이트 해준다. 3. boolean값으로 연합을 찾았는지 확인하며, 연합이 없을 경우 반복문을 종료한다. import java.io...

1. 문제 https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 2. 풀이과정 방법 1. BFS 더보기 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int damage[][] = new ..

1. 문제 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 2. 풀이과정 문제에서 주어지는 x, y를 반대로 생각하는 게 편해서 x를 세로축, y를 가로축으로 생각하고 풀었습니다. 90도 회전하는 방법 1) x증가량 => y감소량 & x감소량 => y증가량 2) y증가량 => x증가량 & y감소량 => x감소량 따라서 nx = 끝점 - (y변화량), ny = 끝점 +(x변화량)이 된다. 다 구하면, 끝점을 업데이트 해..

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인데 여기..