신년맞이 boj - day4

1202 보석 도둑

처음엔 보석 값대로 sort하고 가방 sort해서 무게 들어가는 거 넣는 방법으로 했는데 당연히 시간초과

github.com/proqk/Algorithm/blob/master/greedy/1202%20%EB%B3%B4%EC%84%9D%20%EB%8F%84%EB%91%91_%EC%8B%9C%EA%B0%84%EC%B4%88%EA%B3%BC.cpp

 

여기서 두 sort를 한 이유는, 가격이 높은 보석부터 차례대로 가방 허용 무게에 가장 가까운 보석을 찾기 위해서이다

다르게 말하면 가방 무게 x보다 큰 보석 중에 가장 작은 수를 찾는다 = Lower Bound

그리고 찾은 값을 삭제한다

이진 탐색 트리BST를 사용하면 이 탐색 및 삭제 연산을 O(NlogK)에 할 수 있다

BST로 구현된 C++ stl set을 사용하면 된다

다만 set은 같은 값 중복 저장을 허용하지 않으니까 여기서는 multiset을 사용한다

 

github.com/proqk/Algorithm/blob/master/greedy/1202%20%EB%B3%B4%EC%84%9D%20%EB%8F%84%EB%91%91_%EB%8B%A4%EC%8B%9C.cpp

 

 

2109 순회강연

보석 도둑이랑 비슷하다

d일 안에 와서 강연을 하면 p만큼을 받는다

d=2인 강연과 d=1인 강연이 있으면 굳이 d=2를 먼저 할 필요가 없다. 즉, 강연은 d일보다 작거나 같은 날에 할 수 있다

하루에 강연을 하나만 할 수 있으므로 보석 도둑에서 가방에 하나의 보석만 넣을 수 있던 조건과 같다

 

강연할 수 있는 날에 가까운 강연 중에 강연료가 높은 강연부터 넣으면 되니까

강연 날짜 x보다 작거나 같은 강연 중에 강연료가 가장 큰 수를 찾는다 는 의미가 된다

 

크거나 같은(이상) 혹은 큰(초과) 조건이 아니기 때문에 Lower Bound를 쓸 수는 없고, 큐를 만들어서 가능한 강연들을 전부 넣은 뒤에 큐를 돌면서 그 중에서 가장 강연료가 높은 강연을 선별하는 식으로 구현한다

 

for문은 어떻게 돌면 좋을까? 1일부터 시작해도 되지만 d=2가 있으면 1일도 되고 2일도 되니까, 1일은 선택할 수 있는 강연의 개수가 많다. 그러면 선택의 폭이 좁은 높은 d값부터 탐색을 하면 과정을 좀 더 간략하게 할 수 있을 것이다

 

그리고 priority_queue를 쓰면 자동 정렬이 되므로 큐에 넣은 뒤에 sort하는 과정을 생략할 수 있다

 

github.com/proqk/Algorithm/blob/master/greedy/2109%20%EC%88%9C%ED%9A%8C%20%EA%B0%95%EC%97%B0.cpp

 

 

5545 최고의 피자

문제가 좀 복잡한데 결국 토핑 중에 (토핑 총 칼로리/가격)가 최대가 되는 경우의 값을 구하면 된다

토핑 칼로리/가격은 항상 최선의 선택(가장 높은 값)을 하면 구하고자 하는 값이 나오므로 내림차순으로 정렬한다

 

토핑을 아무것도 올리지 않을 수도 있으니까 초깃값을 아무것도 없을 때의 칼로리/가격으로 설정

그 후 반복문을 돌면서 해당 토핑을 넣었을 때 결과값이 더 크면 넣고 아니면 넣지 않는다

토핑은 내림차순으로 정렬되어 있으며 무조건 높은 값부터 이득이므로 반복문은 이중이 아닌 한 번만 돌아도 된다

 

github.com/proqk/Algorithm/blob/master/greedy/5545%20%EC%B5%9C%EA%B3%A0%EC%9D%98%20%ED%94%BC%EC%9E%90.cpp

 

 

20363 당근 키우기

1. x와 y중에 큰 값을 res에 넣는다. 큰 값 쪽이 온전히 들어가는 게 이득이다

2. x와 y중에 작은 값을 res에 더한다. 작은 쪽도 넣어야 한다

3. res에 x와 y중에 작은 값/10을 더한다. 작은 쪽 물이 들어가면서 빠지게 된 온기만큼 더 해야 한다

 

github.com/proqk/Algorithm/blob/master/greedy/20363%20%EB%8B%B9%EA%B7%BC%20%ED%82%A4%EC%9A%B0%EA%B8%B0.cpp