<백준(파이썬)> 1715번: 카드 정렬하기

 

🤖

 

문제

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

풀이

문제를 너무 쉽게 판단하고 '틀렸습니다.'라는 결과를 맞이하게 되었습니다.

카드 묶음을 오름차순으로 정렬한 후 앞에서부터 순서대로 더하면 답이 나올 것이라고 생각했습니다.

아래 코드의 11~13번째줄과 같이 첫번째, 두번째 숫자는 N-1번 더하고, 마지막 숫자는 1번만 더할 것이라는 개념을 바탕으로 풀이를 작성하였습니다.

이 풀이의 문제는 아래의 예시를 해결할 수 없다는 것입니다.

[15, 20, 30, 32] 가 주어진 경우

첫번째 반복문을 돌고나면

[35, 30, 32] 가 되어 다음번 계산이 30+32가 되어야 하지만

위의 풀이로는 무조건 맨 앞의 두 숫자를 더하는 것으로 가정하기 때문에 35+30의 엉뚱한 계산을 합니다.

잘못된 풀이를 수정하기 위해 파이썬의 heapq를 활용하였습니다.

힙정렬(최소힙)을 이용하면 배열에서 2개의 값을 뽑을때 항상 최소값이 되도록 다룰수가 있습니다.

7~8번째 줄에서 card_mass들을 힙정렬하게 됩니다.

11번째줄 while 반복문으로 들어가는데, card_mass 배열에 값이 하나라도 있으면 반복문을 실행합니다.

12~13번째 줄과 같이 card_mass 배열의 길이가 0이면 반복문을 빠져나옵니다.

15~19번째 줄이 문제의 핵심으로 최소값 2개를 빼와서 acc(누적합)에 더하고, 더하는데 사용된 sum을 heapq를 통해 card_mass에 다시 넣어줍니다.

 

문제가 쉽게 느껴지는 경우 간과한 케이스가 있는지, 문제를 잘못 이해했는지 한번더 깊이있게 고민하는 연습 필요