BOJ 1202번 보석 도둑

1202번: 보석 도둑

 

정답으로 출력할 값이 int의 영역을 벗어나는 것을 예측 못해서 시간을 조금 소비했던 문제였다.

문제 자체는 그리디 알고리즘의 정석에 가깝다고 생각된다.

 

 

 

---

문제에서 주어진 예시는 설명에 적합하지 않은 관계로 아래와 같이 임의로 만든 예시를 가지고 설명을 진행한다.

 

---

이 문제는 가방 1개당 가져갈 수 있는 보석이 1개로 1 대 1 매칭이 된다.

 

용량이 20 짜리 가방에 무게가 1짜리 보석을 넣어도 해당 가방은 가득 찬 처리가 되기 때문에 항상 보석은 가방 개수만큼만 가져갈 수 있다. 그렇다면 가벼운 가방이라도 넣을 수 있는 보석이 있다면 넣는 것이 항상 이득이 된다.

 

또한 가방에 넣을 수 있는 보석이 2개 이상인 경우, 더 비싼 보석을 담을수록 이득이 된다.

 

즉 이 문제에서는 가방을 모두 다 채우는 것 과, 가방을 채울 때 가장 비싼 보석부터 넣는 것을 신경 쓰면 된다.

 

 

 

이제 두 가지 조건중 어떤 조건이 더 우선순위가 높은 조건이 될까 생각해보자.  

 

위와 같은 상황일 때, 가방을 모두 채우는 것 을 우선순위로 둔다면 두 가방에 모두 보석을 담아서 190의 가치를 얻게 되지만, 가장 비싼 보석을 넣는 것에 우선순위를 둔다면 25 용량 가방에 1 무게 보석을 담는 경우가 생긴다.

이를 예외 처리할 수는 있다. 하지만 예외처리를 통한 구현보다는 규칙 자체에 예외가 생기지 않도록 하는 것이 더 깔끔한 규칙(=알고리즘)이라고 할 수 있다.

 

그렇기 때문에, 가능한 모든 가방을 채운다는 것을 1순위로, 넣을 수 있는 것들 중 가장 비싼 보석을 넣는 것을 2순위로 하는 알고리즘을 생각해 본다.

 

 

 

가방을 가벼운 순서로 정렬한 뒤, 해당 가방에 넣을 수 있는 보석 중 가장 높은 보석을 하나씩 제거하는 방법 또한 가능하지만 이를 위해서는 보석을 2중 정렬해야 한다.

보다 간단한 구현을 위해 다중 정렬은 포기하고 보석을 가격 우선으로 정렬하기로 했다.

 

 

이후 다음과 같은 규칙을 따른다.

 

• (규칙 A) 보석 리스트 중 가장 비싼 보석 (=가장 앞의 값) 이 들어갈 수 있는 가방 중 가장 작은 가방을 찾는다.
  • (규칙 A-1) 만약 넣을 수 있는 가방이 없다면 해당 보석을 삭제 (pop) 한다.
  • (규칙 A-2) 만약 넣을 수 있는 가방이 있다면 해당 보석과 가방을 같이 삭제 (pop) 한 뒤 정답에 가산한다.
• (규칙 B) 가방 또는 보석 리스트가 모두 소진될 때까지 규칙 A를 반복한다.

 

 

규칙 A, A-2에 의하여 1/100 보석과 1 가방이 같이 사라진다.

 

25 무게의 보석을 담을 수 있는 가방이 없으므로 규칙 A-1에 의해 25/90 보석을 삭제한다.

 

 

마찬가지로 규칙 A, A-2에 의하여 1/80 보석과 5 가방이 같이 사라진다.

 

 

 

 

 

 

 

 

 

 

 

 

이렇게 임의로 만든 예시의 답을 구할 수 있다.

 

문제의 예시 또한 같은 방식으로 처리가 가능하니 한번 해보자.

 

 

---

 

code

GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지