Algorithm/Greedy

[백준 11047번] 동전 0 (C++)

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 동전 0 문제는 Ai가 Ai-1의 배수이기 때문에 가치가 큰 동전부터 최대한 많이 선택하여 문제를 해결할 수 있습니다. 아래는 전체 코드입니다. #include using namespace std; int n, k, ans = INT_MAX; vector coin; int main(){ ios::sync_with_stdio(0); c..

[백준 1931번] 회의실 배정 (C++)

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 회의실 배정 문제는 그리디 알고리즘을 이용하여 해결할 수 있습니다. 만약 시작 시간이 가장 빠른 것을 선택하고, 이후 종료 시간보다 시작 시간이 크거나 같은 회의 중 시작 시간이 가장 작은 것을 선택한다면, 시작 시간이 가장 빨라도 회의 시간이 긴 경우 사용 가능한 회의의 수가 최대가 되지 않을 수 있습니다. 따라서 종료 시간이 가장 빠른 것을 선택하고, 종료 시간 이후 시작하는 것 중 가장 빨리 끝나는 것을 선택하면 됩니다. 즉, 종료 시간을 기준으로 정렬한 다음, 시작 시간이 전 회의가 종료 시간보다 같거나 ..