BOJ 1715번 카드 정렬하기

1715번: 카드 정렬하기

 

 

문제가 복잡해 보이지만 사실 문제를 단순화하면 리스트 내의 가장 작은 두 수의 합 을 반복적으로 구하는 문제이다.

처음에는 삽입 정렬을 이용해서 처리하려 했으나 시간이 초과되어 우선순위 큐를 이용해야 한다는걸 뒤늦게 깨닳은 문제였다.

 

우선순위 큐는 평소 힙을 이용해서 구현하나, 최초에 삽입정렬로 구현하는 탓에 구현시간이 몇분 남지 않아 그당시 바로 떠올랐던 멀티셋을 이용해 구현했다.

 

---

구현은 너무나도 간단하다. (입력 함수를 나누고, 의미없는 개행을 포함해도 50 line이다)

그래서 이 문제가 왜 리스트내의 가장 작은 두 수의 합을 반복하는 문제인지만 간단하게 설명하고자 한다.

 

이 문제에서 카드묶음은 한번 연산에 사용된뒤, 소모되어 사라지는 형태가 아니다. 다시 리스트로 돌아와서 다시 연산에 사용되는 것 이다.

 

즉 큰 카드 뭉치를 연산에 여러번 사용할 수록 최종 답이 커지는 것이고,

작은 카드뭉치를 여러번 연산에 사용 할 수록 최종 답이 작아지는 것 이다.

 

그러므로 연산을 하는 순간, 리스트에 있는 카드 뭉치중 가장 작은 2개를 이용하는 방법을 반복하는 것이 최소값을 얻는 방법이다.

---

 

code

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