골드 이상 풀이 정리 1주차

1. 동전 (BOJ 9084)

dp, knapsack

 

동전 하나를 잡고 그 동전의 값 이상부터 n까지 이전 값을 불러오면 된다. 당연히 0원은 무조건 만들 수 있으니 1로 초기화 해서 시작하면 된다.

 

2. 겹치는 선분 (BOJ 1689)

sweeping, sorting

 

imos법 같이 돌리면 된다. 즉, 시작 점은 1로 두고, 끝 점은 -1로 둬서 점의 위치를 중심으로 정렬해준다.

예를 들어 (1, 5), (3, 6), (2, 3)가 있으면 (1, 1), (2, 1), (3, -1), (3, 1), (5, -1), (6, -1)로 될 것이다. 그리고 좌표 하나하나씩 순서대로 확인해서 변수에 +1, 혹은 -1을 하고 최댓값을 갱신하면 된다. 당연히 -1이 1보다 작으므로 먼저 계산되기 때문에 '선분의 끝 점에서 겹치는 것은 겹치는 것으로 세지 않는다.'에 만족한다.

 

3. 보석 도둑 (BOJ 1202)

sorting, priority queue, greedy

 

일단 보석의 가격을 가장 큰 것을 넣는게 맞고 이때 무게가 넘지 않게 조건을 만족하도록 해야한다. 가장 용량이 작은 가방부터 차근차근 보석을 넣는데 이때 가격이 가장 큰 것을 넣으면 된다. 최소 힙, 최대 힙을 사용해서 최소 힙에는 (무게, 가격)을 넣고 가방의 용량을 작은 것부터 반복문을 돌리면서 조건에 모두 만족하는 모든 보석을 최대 힙에 넣어준다. 그리고 하나 이상 최대 힙에 있다면 그 값을 더한다. 이전에 만족은 했지만 넣지 못한 보석은 그 다음 가방의 최대 용량보다 항상 작거나 같으므로 반복문이 돌때마다 하나씩 최대 힙에서 빼면 된다는 의미이다.

 

(5, 3), (5, 7), (7, 9)가 있고, 가방은 5, 6이라고 할 때, 처음에는 5의 가방에 넣을 수 있는 보석은 (5, 3), (5, 7)이다. 즉, 최대 힙에 3과 7을 넣는다. 보석은 하나밖에 못 넣으므로 가장 가치가 큰 7을 5의 가방에 넣고, 6일 때는 최소 힙에서 넣을 수 있는 보석은 존재하지 않지만 최대 힙에는 현재 3이 있고 이때 이 보석의 무게는 5였으므로 6보다 작기 때문에 6의 가방에 3을 넣으면 된다.

 

4. Fibonacci Lucky Numbers (BOJ 32454)

pisano period, euler_phi

 

길어져서 게시글을 따로 뒀다.