Ikjo's Technology blog

문제 설명 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 접근 방법 문제에서 요구하고있는 회의실을 사용할 수 있는 회의의 최대 개수를 구하기 위해서는 우선 가장 일찍 시작하는 회의 시간에서 가장 늦게 시작하는 회의 시간 까지 겹치지 않으면서 사이사이에 가능한한 회의들이 다닥다닥 붙어있어야 합니다. 이러한 환경(?)을 만들기 위해 우선 입력받은 회의실 정보를 '끝나는 시간'을 기준으로 오름차순 정렬하고 만일 같다면 '시작 시간'을 기준으로 오름차순 정렬합니다. public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR..

문제 설명 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 회고 해당 문제는 BFS를 이용하여 풀이할 수 있었는데, 익은 토마토를 기점으로 익지 않은 토마토들이 점차 확산되어가며 익어간다는 점 그리고 익는데 며칠이 걸리는지를 구해야 한다는 점에서 BFS를 떠올릴 수 있었습니다. 이때 DFS를 사용하지 않았던 이유는 익은 토마토들이 여러 개 있을 때 익은 토마토들을 기점으로 동시 다발적으로 익지 않은 토마토들로 확산되어 갈텐데 DFS는 우선적으로 하나의 익은 토마토를 기점으로 확산시..

문제 설명 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 풀이 회고 해당 문제에서 요구하는 것은 오름차순으로 동전의 가치가 주어졌을 때 해당 동전들로 k원을 만드는데 필요한 동전 개수의 최솟값입니다. 이 문제는 그리디 알고리즘의 유형으로 정답을 구하기 위해서는 가장 가치가 큰 동전들을 토대로 k원을 구성해야합니다. 이때 입력 받은 동전의 가치들을 저장한 배열은 오름차순으로 정렬되어있으므로 배열의 끝 부분부터 k원을 나누면서 몫이 존재할 때(1 이..

문제 설명 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 회고 해당 문제는 이분 탐색을 이용하여 해결할 수 있었습니다. 우선 문제에서 요구하는 것은 최소 m 만큼의 나무 높이를 얻기 위해 n개의 나무를 자를 절단기의 최대 높이를 구하는 것입니다. 우선 이분 탐색을 위해 다음과 같이 n개의 나무의 높이를 배열 각각의 요소에 할당한 후 오름차순으로 정렬합니다. for (int i = 0; i < n; i++) { trees[i] = Integer.parseInt(st..

문제 설명 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 회고 우선 해당 문제에서 요구하는 것은 49가지 수(1~49) 중 임의의(7~12개의) 주어진 수들의 집합에서 6개의 수를 골라 만들 수 있는 경우의 수입니다. 즉, 주어진 수들에 대해 6개의 조합을 구하는 것입니다. 자바를 통해 조합을 구할 수 있는 방법에는 여러가지 방법이 있겠지만, 대표적으로 백트래킹을 이용하는 방법과 재귀함수를 이용하는 방법이 있습니다. 저 같은 경우에는 평상시 익숙한 '재귀함수'를 이용하여 문제에 접근해보았는데..