백준 23575 - Squid Game

 문제를 요약하자면, 세 개의 물통중 두 물통을 골라 양이 더 적은 물통의 양을 2배하고, 반대쪽 물통에서는 그만큼 물을 뺄 때 한 물통의 양을 0으로 만들어야 한다는 것이다. 원래대로라면 수학적으로 깔끔한 풀이가 있지만, 본 글에서는 다른 방법을 적용하였다.

 본 글에서는 해당 문제를 dlas로 해결하였다. dlas는 특정한 상태를 정의하여 그 최적해를 구하는 기법으로, 본 글에서 자세히 소개하지는 않겠다.

 우선, 아주 간단하게 랜덤으로 물의 양을 바꾸기만 해도 그 크기가 적당히 작아지는 것을 기대할 수 있다. 물론, 이 경우 수 분이 걸리기 때문에 실제 풀이로 적용 가능할지는 잘 모르겠다. 핵심은 이러한 랜덤을 dlas로 발전시키는 것이다. 해당 문제에 대한 상태를 시행을 적용하는 방법의 배열로 정의하자. 그렇다면 상태를 전이하는 함수는 해당 배열 내의 어떤 방법을 바꾸는 것이고, 그 평가함수는 한 물통 안에 있는 물의 양의 최솟값이 될 것이다. 이러한 방식으로 dlas를 구현하면 문제가 해결된다.

 사실, 랜덤 데이터를 만들고 진행해보면 생각보다 그 속도가 빠르지 않음을 알 수 있다. 필자의 코드는 대부분의 경우 1초 이내로 답이 나왔지만, 일부 상황에서는 3초가 걸릴 정도로 느려지기도 했다. 다만 데이터가 이런 핵심적인 문제를 공격하지는 않았기 때문에 안정적으로 해결되었고, 심지어 그 시간이 68ms가 나왔다.