문제 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 풀이 그리디 문제로 새로운 테이프를 언제 붙여줘야 하는지를 계산하는 문제이다. 물이 새는 곳의 위치는 입력받아 배열에 저장하고, 이를 오름차순으로 정렬한다. 정렬된 배열을 기반으로 테이프를 붙여 주는데, 이전에 붙였던 테이프가 현재 물이 새는 곳에도 붙일 수 있다면 개수를 세지 않고 넘어간다. 붙여지는 범위는 현재 위치 + 테이프의 길이 - 1로 정하면 된다. 테이프를 붙이는 범위를 현재 위치 + 테이프의 길이 - 1로 정하는 이유는 테이프..

문제 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 이 문제에서는 각 알파벳에 가중치를 계산하고, 그 가중치에 따라 알파벳에 숫자를 할당해주어 계산하면 최대값이 계산된다. 먼저 26개의 알파벳에 대한 가중치를 저장하는 배열을 선언한다. 입력받은 문자열에서 각 알파벳의 자릿수에 따라 10의 배수로 가중치를 부여한다. 예를 들어 예제 입력 2에서 GCF는 G: 100, C: 10, F: 1,의 가중치가 부여되고, ACDEB는 A: 10000, C: 1000, D: 100, E: 10, B: 1의 가중..

문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 이 문제의 유형은 활동 선택 문제(Activity Selection problem)라고하며 대표적인 그리디 문제이다. 활동 선택 문제란 각 활동의 시작 시간과 종료 시간이 주어졌을 때, 한 사람은 한 번에 하나의 활동만 수행할 수 있다고 가정하며, 한 사람이 최대로 수행할 수 있는 활동의 수를 찾는 것을 목표로 하는 것이다. 선택할 수 있는 활동이 많아지려면, 서로 겹치지 않는 활동에 대해 종료시간 빠른 경우를 선택해야 한다. 따라서 활동들을 종료시간을 기준으로 정렬하고 선택한다. 가장 먼저 종료하는 활동을 선택하고, 두 번째 활동부터 활동의 시작 시간이 마지막으로 ..

문제 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 현재 사람이 인출하는데 필요한 시간은 앞으로 인출할 사람들이 기다려야하는 시간이다. 그러므로 총 시간은 시간이 적게 걸리는 사람이 먼저 인출할 때 최소가 된다. 입력받은 배열을 오름차순으로 정렬하는 것이 이 문제에서 사용되는 그리디 알고리즘이다. for문을 통해 현재 사용되는 시간 $\times$ 남은 사람의 수를 합한 값을 출력한다. 코드 import java.util.* fun main() { val br = System.`in`.bufferedReader() val bw = S..

문제 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 이 문제는 이중 반복문(3의 배수 + 5의 배수의 합)으로 해결할 수도 있지만, 효율적인 풀이를 위해 그리디 알고리즘과 DP를 이용할 수 있다. - 그리디 풀이 1. N이 5의 배수라면 답은 N/5 2. N이 5의 배수가 아니라면 3kg 에 한 번 담고(cnt++, N -= 3) 다시 반복문을 실행한다. 3. N이 0보다 작아지면 답은 -1 - dp 풀이 N이라는 숫자를 만들기 위해서 (N - 3) + 3 또는 (N - 5) + 5 의 경우로 나눠 볼 수 있다...