MingyuPark

문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 아이디어 그리디 알고리즘으로 접근할 수 있다. 그 근거를 살펴보자. 지금 시점에 시작할 수 있는 회의들 중에서 가장 빨리 끝나는 회의를 진행하면 된다. 시작 시간을 고려하면 안된다. 시작 시간 자체는 다음 회의를 탐색하는 데에 있어서 기준이 될 수 없다. 이번 회의가 일찍 끝나면 끝날수록 더 많은 다음 회의를 고려할 수 있다. 결론은, 일단 모르겠고 제일 먼저 끝나는 걸 찾자. 이다. 예를 들어보자. 회의 시간이 (1, 4), (2, 3), (3, 5) 라고 하자. 시작 시간 기준으로 정렬하면 (1, 4) ..

문제 https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 아이디어 한 쪽 물병에 담긴 물을 나머지 모두 붓기 때문에 물병에 있는 물은 2의 거듭제곱(2^x) 으로 표현할 수 있다. K개를 넘지 않는 이라는 표현이 핵심이다. 가능하면 x가 큰 물병이 많은 게 좋다는 뜻이다. 1026개의 물병이 있었다고 해보자. 이 때는 2리터짜리 물병 513개보다는 1024리터짜리 물병 하나와 2리터짜리 물병 하나가 좋다는 뜻이다. (그렇다고 무조건 적은 것을 찾는 게 ..

문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 아이디어 N킬로그램에서 필요한 봉지의 수를 f(N)이라고 하자. 이 경우 봉지를 하나 추가하는 경우는 3kg 봉지를 하나 추가하는 경우와 5kg 봉지를 하나 추가하는 경우 둘 중 하나이다. 즉, f(N) = f(N-3) + 1이거나 f(N) = f(N-5) + 1이 될 수 있다. f(N-3)과 f(N-5)의 대소관계를 비교해야 한다. 봉지 수가 가장 적은 경우를 구해야 하기 때문에 f(N-3)과 f(N..