문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 코드 import java.util.*; import java.io.*; public class Main { static int n; static int board[][]; static boolean check[]; static int min = Integer.MAX_VALUE; public static void main (String[] args) throws java.lang.Exception { Buffer..
문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 풀이 BFS 처럼 풀었지만 BFS문제는 아니고 BFS문제 같은 구현 문제다. 문제에서 나타나는 그대로 구현하면 된다. 주의해야 할 것은 다음 두가지다. 1. 후진 2. 반시계 방향으로 돌기 1. 후진을 수식으로 나타낸다면 다음과 같이 나타낼 수 있다. (현재 방향 + 2 ) % 4 후진을 한다는 것은 현재방향과 반대이기 때문에 2를 더한후 4..
문제 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이 BFS 또는 플로이드 와샬을 이용하여 풀 수 있다. 플로이드 와샬로 풀 경우에는 시작정점과 도착정점의 연결여부로 풀 수 있다. 코드 BFS import java.util.*; import java.io.*; public class Main { static class Point{ int x; int y; public Point(int x, int y) { this.x = x; thi..
문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 DP 문제 DP[ i ] 는 i원이 만들어지는 경우의 수를 나타낸다. 예를 들어 1원, 2원, 5원으로 2원을 만든다면 DP[2] 는 2가 될 것이다. DP식은 다음과 같다. DP[num] = DP[num] + DP[num - coin] 문제에 나와있는 예시가 입력으로 주어졌을때 1. DP에 1원으로 1원~10원까지 만들어질 수 있는 경우의 수를 넣는다. 2. DP에 1원과 2원으로 1원..
문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 코드 BFS를 이용해서 풀면된다. import java.util.*; import java.io.*; public class Main { static int m, n; static boolean check[][]; static int dx [] = {1,0,-1,0}; static int dy [] = {0,1,0,-1}; static int area []; static ..
문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 import java.util.*; import java.io.*; public class Main { public static void main (String[] args) throws java.lang.Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int n = Integ..
문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 import java.util.*; import java.io.*; public class Main { static int n; static int arr[][]; static int result = 0; static int dx [] = {1,0,-1,0}; static int dy [] = {0,-1,0,1}; public static void main (String[] args) thro..
문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 코드 BFS import java.util.*; import java.io.*; public class Main { static ArrayList arr[]; static int visit[]; static int a, b; static int result = -1; public static void main (String[] args) throws java.lang.Ex..
문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 코드 import java.util.*; import java.io.*; public class Main { static int n; static int arr [][]; static boolean check [][]; static int house []; static int dx [] = {-1,0,1,0}; static int dy [] = {0,-1,0,1}; public static v..
문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 다이나믹 프로그래밍으로 풀었다. (내 힘으로 풀었다 드디어 발전하는듯) DP 배열은 특정 부분의 스티커를 때었을때의 누적 최대값을 나타나도록 만들었다. 예를 들자면, 현재 색칠한 부분의 스티커를 뗀다고 해보자. 이부분의 위치는 (1,2)가 될것이다. 노란색 부분의 dp 값은 다음 두가지가 될 수있다. 1. 왼쪽 대각선 방향의 dp 값 + 현재 스티커 값 (노란색 스티커를 뗄수..
