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

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

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변화량)이 된다. 다 구하면, 끝점을 업데이트 해..