문제 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 풀이 이 문제는 그리디 알고리즘을 사용하여 해결하는 문제다. 그리디 알고리즘이란 현재 상황에서 최선의 선택을 고르며 해답을 찾는 알고리즘이다. 유의할 점은 그리디 알고리즘은 항상 최적해를 보장하는 것이 아니라는 것이다. 예를 들어 어떤 경로 이동에서 매 순간 최적을 따라가면 1 - 1 - 1 - 100 순서로 이동하지만, 1 - 1 - 10 - 10 으로 움직이는 방법이 있을 수 있기 때문이다...

문제 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 풀이 단순하게 2중 for문을 사용하여 판매의 최대값을 갱신해가며 계산하는 풀이는 시간초과가 발생한다. 대신 역방향 탐색을 활용하여 해결해야 한다. 주식으로 최대의 이익을 보려면 주식을 구입한 가격과 판매하는 가격의 차이가 가장 커야 한다. 역방향 탐색을 통해 판매하는 가격의 최대값을 얻을 수 있다. 먼저 마지막으로 입력받은 가격을 최대값으로 설정하고 역방향 탐색을 시작한다. 탐색 중 현재 값이 최대값보다 작다면 둘의 차이가 얻을 수 있는 가장 ..

문제 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 병든 나이트는 오른쪽 위나 아래로만 움직일 수 있으며 4칸 이상 방문한 경우에는 모든 방향으로 최소 한 번은 움직여야 하기 때문에 체스판의 크기에 따라 움직임이 제한된다. - N = 1 아무 방향으로 움직일 수 없기 때문에 답은 1이다. - N = 2 2번과 3번 방향으로만 움직일 수 있기 때문에 답은 (M+1)/2이다. 그러나 최대 4칸까지만 이동이 가능하다. - N >= 3 1) M < 7: 1번과 4번 방향을 번갈아가면서 이동하는 것이 최대로 방문하는 방법이다. 따라서 답은 M이다. 그러나 최대 4칸까지만 이동..

문제 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 풀이 행렬 A와 B를 반복문을 통해 비교한다. 만약 값이 다르다면 A 행렬을 해당 위치를 기준으로 3 x 3 부분 행렬을 뒤집고 횟수를 세어준다. 모든 연산을 마친 후 두 행렬이 다르다면 -1을 출력하고 같다면 뒤집은 횟수를 출력한다. 코드 fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() val (rows, cols) = br.readLine().split(' '..

문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 LectureTime 데이터 클래스를 정의하여 Comparable 인터페이스를 구현한다. 시작시간을 기준으로 오름차순 정렬하도록 고 만약 시작시간이 같다면 종료시간을 기준으로 정렬한다. 입력받은 시간을 LectureTime 배열에 저장하고 이 배열을 정렬해준다. 우선순위 큐를 선언하고 첫번째 수업의 종료 시간을 큐에 넣는다. 배열을 순회하면서 만약 현재 강의의 시작 시간이 우선순위 큐의 최상단의 강의의 종료 시간보다 작거나 같으면 해당 강의는 해당 강의실에서 진행 가능하므로 우선순위 큐에서 poll(..