코드로 채우는 블로그

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 전에 풀었던 이친수와 비슷한 DP 문제이다. 0은 두개 연속와야 하는 경우를 생각해준다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { int..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 꽤 신기했던 DP 문제였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N; public static void main(String[] args) throws IOException { BufferedReader..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 기존 동전에서 조금더 어려워진 버전이다. 동전을 입력받고 해당 동전으로 현재 상황에서 만들 수 있는 가치들을 보며 최소횟수인 경우에만 갯수를 바꿔준다. //최대 수로 채우기 Arrays.fill(dp, 10001); dp[0] = 0; for (int i = 1; i

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 꽤 재밌었던 DP 문제이다. 각 스티커를 골랐을 때 가능한 최대값을 구하고 마지막 열의 두 스티커 중 더 큰 값을 출력하면 된다. 쉽게 말해서 스티커를 뗄 때마다 그 상황에서 가장 큰 수를 구하는 것이다. 위 사진을 보자 첫번째 열에서 50을 떼어내면 무조건 50이 크고, 30을 떼어내면 30이 크다. 두번째 열에서는 10을 땔 경우 앞에서는 30을 떼어내고, 50을 땔 경우 앞에서는 ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP 문제라 풀이 방식이 매우 많다. Bottom-Up 방식도 있고 Top-Down 방식도 있다. import java.io.*; import java.util.*; public class Main { static int[] a; public static void main(String[] args) throws IOException { int N; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseI..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 기본적인 DFS와 BFS 문제이다. 입력받은 노드들을 각각 DFS, BFS로 출력하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; imp..

https://www.acmicpc.net/problem/1493 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net 박스를 어떻게 나눠야하는지 생각하는 것이 어려웠다. 박스에 넣을 수 있는 가장 큰 큐브를 넣은 후 오른쪽, 왼쪽, 위 3가지로 남은 공간을 나누어 다시 재귀 호출하는 분할 정복 방식을 이용했다. public static void sol(int l, int w, int h) { if (l == 0 || w == 0 || h == 0) return; int powd;..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 2가지 방식을 생각했다. 첫번째 방식 날짜를 뒤에서 부터 생각하며 각 날짜마다 가장 높은 과제를 풀도록 하는 방식 예제 1번을 예시로 하면 가장 마지막 마감일이 6일이다. 6일에 할 수 있는 과제 중 가장 큰 과제는 마지막 과제이므로 +5 5일에 할 수 있는 과제는 없다. 4일에 할 수 있는 과제 중 가장 큰 과제는 첫번째 과제이므로 +60 3일에 할 수 있는 과제 중 가장 큰 과제는 두번째 과제이므로 +40 2일에 할 수 있는 과제 중 가..

https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 집중국을 어디다가 놔둬야 하는지 알아내는 것이 중요한 문제이다. 센서들을 거리에 맞게 정렬하고 사이거리를 구한다. 사이거리가 긴 부분을 제외하고 집중국을 설치하도록 한다. 예제 1번에서 센서를 거리에 맞게 정렬하면 1 3 6 6 7 9 이다 각 사이 거리는 2 3 0 1 2 인데 2개의 집중국을 설치해야한다면 딱 한 센서 사이를 기준으로 나누면 된다. 즉, 사이 거리가 3..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 간단히 말해 멀티탭에 연결한 플러그를 빼는 횟수를 최소화시키는 문제이다. 처음에는 남은 용품의 각각의 수를 계산하고 가장 적게 남은 상품을 교체하는 방식으로 잘못 풀었다. 올바른 방식은 다음 용품을 꽂아야 할 때 빼야 하는 플러그를 구하는 기준은 이후에 꽂는 순서가 가장 뒤인 용품이다. 예를 들어)2 7 / 2 3 2 3 1 2 7 에서 네번째 용품까지는 플러그를 뺄 일이 없다. 1을 연결해야 할..