[프로그래머스] 금과 은 운반하기 (LEVEL 3)

월간 코드 챌린지 시즌3 9월 3번으로 출제된 문제이다.

처음엔 4.2점, 다음엔 12.5점, 20.8점을 얻고 한참 고민하여 만점을 받아 풀이를 작성해본다.

https://programmers.co.kr/learn/courses/30/lessons/86053

코딩테스트 연습 - 금과 은 운반하기

---

접근 방법

T가 딱히 10^5라 이분탐색을 떠올리기 어려웠을 수 있다. 그러나 어차피 운반하는데에 걸리는 최소 시간을 묻는 문제이며, 이는 결정여부를 따지는 문제로 충분히 이분탐색을 떠올릴 수 있다.

따라서 O(NlgT) 또는 O(NWlgT) 풀이로 잘 작성하면 될 것이다.

 

자세한 해설은 아래 공식 블로그에서 확인가능하다.

https://prgms.tistory.com/101

월간 코드 챌린지 시즌3 9월 해설

 

4.2점 풀이

4.2점 풀이는 항상 금, 또는 은만 최대치로 옮기는 풀이이다. 따라서 테스트케이스 1번이 제대로 나오지 않는 풀이이며, 이 풀이여도 제출하면 4.2점을 얻는다.

 

12.5점 풀이

12.5점 풀이는 두 개의 변수 Gold, Silver의 합이 항상 w[i] * (1 + (mid / t[i])) / 2임을 이용하여 O(NlgT)로 접근은 잘 했으나, 길이 2개 이상일 때, 합에서 gold나 silver를 잘못 제외했을 경우 발생할 것이다. 나의 경우, gold의 값이 누적합으로 계속 더해지고 있었는데, 합-gold 를 하는 과정에서, gold 자체가 아닌 gold 누적합을 빼버려서 12.5점을 받았다.

즉, 계산실수로 12.5점을 받았을 확률이 크다.

 

20.8점 풀이

20.8점 풀이는 Gold, Silver의 합이 반드시  w[i] * (1 + (mid / t[i])) / 2가 아님을 놓쳤을 때 발생한다.

G[i], S[i]는 한정돼있기 때문에 min으로 적절히 처리하는 것을 놓쳤을 때 발생하는 점수이다.

사실 이 부분에서 굉장히 헤맸는데, 디버깅과정에서 겨우 찾아내서 만점을 받을 수 있었다.

 

만점풀이

20.8점 풀이에서 제대로 풀면 만점이 나온다.

대부분은 20.8점이거나 12.5점이었는데, 예외조건이나 계산처리가 조금 많은 문제여서 계산실수를 하지 않았을까 생각된다. 

---

생각보다 더 힘든 문제였다...