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

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

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

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마다 자신의 왼쪽에 있는 블럭 중 최대..