구현
코드
import sys input = sys.stdin.readline n = int(input()) value = [int(input()) for _ in range(n)] value.sort(reverse=True) cost = 0 for i in range(0, len(value), 3): s = value[i:i+3] cost += sum(s) - min(s) if len(value) % 3 != 0: s = value[len(value)-1] print(cost + s) else: print(cost)
설명
- 잘못된 접근
을 하기 쉬워지는 문제같다. 처음에 시간복잡도를 보지 않고 단순 3개씩 전부 묶어 그중 조건에 맞는 가장 작은 최소의 비용을 찾으려고 '완전탐색'을 생각했지만 시간복잡도를 계산해본 결과 정말 말도 안되는 복잡도를 갖게 된다.
예를들어 '유제품의 개수는 10만개' 최대 10만개까지 주어진다.
그렇다면 완전탐색으로 하게 된다면 10만개 만큼 for루프가 돌아가게 되고 3개씩 묶음의 대한 10만개 // 3만큼 for문이 필요해지게 된다. 왜냐하면 처음 값을 기준으로해서 3개를 먼저잡아주면 처음에 잡아준 값이랑 중복해서 묶여버리면 안된다. 그렇다는건 i, i+3 만큼 벌어진 위치에서부터 시작을 해야 된다는 것을 의미하고 이는 곳 "한 기준에 대한 하나의 묶음" 이라고 볼 수 있다. 그렇게 되면 두개가 묶여진 상황에서 묶여질 수 있을 만큼 묶여져야 하기 때문에 for문의 개수는 10만개 // 3만큼의 개수만큼 필요로 되어진다. 적어도 약 3만개 정도 for문이 필요해지게 되는데 말이 되지 않는다...
- 올바른 접근
힌트를 보고도 도저히 감이 오질 않아 다른 사람의 풀이를 참조했지만 참 신기한 문제라고 생각이 들었던게 배열로 묶어버리는 과정 자체가 문제의 해석만 깊게 파악해본다면 풀 수 있었던 문제 같았다.
우선 가장 처음으로 이해해야 되는 것은 "최소비용"이다.
최소비용은 가장 작은 비용을 의미하며 문제에서 조건은 두개가 주어진다.
첫번째 조건
'유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 됩니다'
이 조건이 의미하는 바는 3개를 한번에 산다면 할인을 해준다는 것이다. 그리고 그때 묶여진 것들 중에서 가장 작은 값은 '무료로' 지불하게 해준다는 것이다.
그럼 최소비용을 만들기 위해서 할인을 많이 받으면 좋다는 것을 알 수 있다 왜냐하면 정가를 주고 내는 것보다 3개씩 묶어 할인을 받는게 전체적인 가격을 낮출 수 있기 때문이다.
이어서 3개씩 묶으면 가격이 낮춰지는데 어떤 기준으로 묶어야 할지를 생각해야 했다. 이는 곧 3개씩 묶으면 가장 작은 숫자, 가장 큰 숫자 뒤섞여 버린다. 조금만 생각해본다면 '가장 큰 값들을 무료로 지불하게 만든다면 전체적인 가격은 낮춰질것이다.' 이 말은 즉 3개씩 묶는 것을 가장 큰 값들로만 묶어주면 그 중 가장 작은 값은 전체를 보고 봤을때 큰 값에 속한다고 볼 수 있다. 그럼 그 일부분의 값들 중 가장 작은 값은 결국 가장 큰 값들 중 가장 작은 값을 무료로 지불하게 만든다는 걸 알 수 있다. 그렇게 되면 모든 경우를 다 찾아보지 않아도 가장 큰 값들 중 작은 값들이 사라짐으로 인해 전체 가격은 낮아질 수 있다는 걸 알 수 있다. 따라서 모든 3개씩 묶어준 값들중에서 가장 작은 값만 빼주고 cost에 합산해준다면 첫번째 조건에 부합하는 내용이된다.
두번째조건
'한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 합니다.'
두번째 조건 같은 경우 3개의 유제품을 사지 않는다는건 결국 3개 미만의 낱개짜리로 되어져 있는 것들을 구입한다는 얘기가 된다. 그럼 위 1번 조건에서 3개씩 묶어놨기 때문에 나머지가 생기게 되는 순간이 있을 수 있고 그렇지 않을 수 있다. 왜냐하면 3의 배수는 항상 나머지가 0이기 때문이다. 그렇다는 말은 3개씩 묶여져 남는 낱개짜리가 없다는 걸 의미하고 남는게 있다는 것은 곧 3의 배수가 아니라는 소리다. 그럼 남는 것만큼은 정가를 지불해주면 되므로 3의 배수와 3의 배수가 아닌 것으로 구분해서 3의 배수는 cost가 나눠진 만큼의 계산결과 값이 그대로 출력이되며 그렇지 않은 경우는 남겨져 있는 부분의 값을 더해준다면 가능하다.
위 식에서는 첫 for문에서 max-min을 빼고 있으므로 '유제품의 개수가 3개미만' 즉 1개 두개 일때를 생각해본다면 분명 max-min값을 뺀다 하지만 두번째 조건을 통해서 빼었던 값을 다시 더해 '모든 값의 대한 정가를' 구하게 된다.
