코드로 채우는 블로그

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 처음에는 어떻게 풀지 엄청 헷갈렸다. 하지만 잘 생각해보면 매우 간단하다. 무조건 현재 시작할 수 있는 회의들 중 제일 빨리 끝나는 회의를 선택하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; public class Main { p..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 가장 쉬운 버전의 동전 문제이다. 단순히 가장 큰 동전부터 최대한 많이 사용하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public clas..

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 두가지 방식을 생각했다. 첫번째는 1001개 크기의 배열을 선언하고 0으로 초기화한다. 입력받은 구멍의 위치의 배열을 1로 설정하고 반복문을 돌린다. 반복문의 인덱스 i를 1씩 증가하면서 구멍을 확인하고 발견하면 테이프를 붙인다. 만약 테이프를 붙이면 반복문의 인덱스를 테이프의 길이만큼 더한다. 이를 반복한다. 두번째는 입력받은 구멍을 오름차순으로 정렬하고 테이프를 붙이면 어느 길..

https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net Case 1 20일의 휴가 동안 연속하는 8일 중 5일만 사용할 수 있다. 즉, 5일 사용가능 + 3일 사용불가능 + 5일 사용가능 + 3일 사용 불가능 + 남은 일수(20 - 5 - 3 - 5 - 3 = 4) = 20일이다. Case 2 17일의 휴가 동안 연속하는 8일 중 5일만 사용할 수 있다. 즉, 5일 사용가능 + 3일 사용불가능 + 5일 사용가능 + 3일 사용 불가능 + 남은 일수..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 이 문제를 풀면서 백트래킹과 DFS의 차이가 헷갈렸다. 중간에 아닌것 같으면 되돌아가는 것이 백트래킹, 끝까지 가는 것이 DFS라고 하는데 다른 풀이를 보면 거의 같은 코드인데 어떤 사람은 백트래킹, 어떤 사람은 DFS라고 한다.... 더 헷갈린다. static public void dfs(int sum, int index) { if (index >= N) re..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net public static void main(String[] args) throws IOException { String input; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); input = br.readLine(); StringTokenizer st = new StringTokenizer(input);..

https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input; int result = 0; N = Integer.parseInt(br.readLine()); a = new int[N][3]; for..

https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 브루트 포스 문제를 풀 때마다 이렇게 푸는게 맞는지 확신이 들지 않는다. 더 좋은 풀이가 있을것 같으면서도 없는..게 문제인거 같다 그냥 무작정 모든 삼각수를 3번 더해서 입력한 값이 되는지 확인하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public cl..

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 처음에는 이게 브루트포스로 다 하는게 맞나 싶은 문제였다. for (int i = 0; i max) max = result; // 다시 복구 swap(n, i, j, i, j + 1); } if (i + 1 < N && ..

https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 브루트포스 문제이다. 입력 받은 수보다 작은 수 중 생성자인 가장 작은 수를 찾으면 된다. 단순히 반복문으로 작은 수부터 찾았다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void ma..