[백준] #18789 - 814 - 2

18789번: 814 - 2

 

요약 및 후기

수작업 -> 표 전체 무작위 생성 코드 작성 -> 표 일부 무작위 수정 및 개선 -> 보조 점수 metric 추가 -> 성공

 

결과적으로 문제를 해결하는데 성공했지만 효과적인 방법은 아닌 것 같다. 원래 이 분야가 그렇다지만 이렇게 하면 좋을까?라는 생각으로 무한한 실험을 하는게 썩 똑똑하게 풀었다는 생각은 들지 않는다. 그래도 독특한 문제 스타일을 경험해서 재밌었고 첫 루비 문제 해결이라 뿌듯하다.

아이디어 1: 수작업

처음에는 수작업으로 0부터 9까지 고르게 채워넣어 8*14의 표를 완성하였다. 나름 괜찮게 배치하였다고 생각했지만 점수는 200점을 넘기기 힘들었다.

아이디어 2: 무작위 생성

점수를 계산할 수 있는 코드를 작성하고 무작위 생성으로 표를 채워넣어 충분히 높은 점수가 나올 때까지 반복하였다. 하지만 역시 500점 이상의 표는 거의 발견되지 않았다.

아이디어 3: 부분 개선

위에서 무작위 생성으로 얻은 표 중 그나마 점수가 높은 표를 골라 부분적으로 개선하고자 하였다. 개선 방법은 다음과 같다.

1. 표의 전체 중 한 칸을 골라 0부터 9까지의 수 중 그 칸의 원래 수를 제외한 다른 수로 변경한다.
2. 총 9개의 표 중 제일 점수가 높은 표를 선택한다.
3. 1과 2를 반복한다.

이 방법으로 노가다를 충분히 진행한 결과 2881점까지의 점수를 높일 수 있었다.

아이디어 4: 지역해 탈출

위의 방법으로 점수가 더 높아질 것이라 기대했지만 그 속도가 매우 느렸다.  이유는 하나의 숫자만 변경해서는 지역해에 갇히기 쉽기 때문이었다. 즉, 어떤 안 좋은 구덩이에 빠져 두 개 혹은 세 개의 표를 순환하는 경우가 생기곤 했다. 사실 이를 미리 관찰하고 임의로 숫자를 수정해왔었다. 이 때문에 위에서 노가다를 진행한 것이다.

 

이러한 현상을 줄이기 위해 다음과 같이 전략을 수정했다.

1. 표에서 임의로 일부 열과 행을 제외하고 나머지 칸 중에서 몇 개를 선택한다.
2. 1에서 선택한 칸들에 임의로 일부 숫자를 제외하고 나머지 숫자들만 선택하여 집어 넣는다.
3. 2에서 만든 표들 중 점수가 제일 높은 표를 선택한다.
4. 1, 2, 3을 반복한다.

이렇게 코드를 변경한 결과 표의 구성이 순환하는 현상이 줄어들었다. 점수가 진동하면서 점차 상승하는 추세를 보였고 이를 통해 3799점의 표까지 발견하였다.

아이디어 5: 보조 점수 metric

위의 방법에서 한계를 느꼈다. 아무리해도 점수가 오르지 않았다. 추측한 이유는 다음과 같았다. 표의 몇몇 칸을 수정하며 당장의 점수를 조금씩 높이는 것은 미래에 더 높은 점수를 획득할 수 있는 '이미 적절히 배치된 조합'들을 제거시킬 수 있다는 생각을 하게 되었다. 예를 들어, 3899이라는 숫자를 읽을 수 있게 만들기 위해 9가 써있는 칸을 8로 수정하면 그 수정이 이미 존재하는 3900대의 숫자 배열을 모두 제거할 수 있다는 것이다. 때문에 미래에도 좋은 점수를 얻을 수 있는 표를 고려해야 했다. 이를 위해 다음과 같은 점수 metric을 생각하게 되었다.

 

1000부터 9999까지의 수 중 읽을 수 있는 수의 개수

 

위의 metric을 기반으로 여러 개의 괜찮은 샘플 표를 얻었다. 아이디어 4에서 점수 metric만 변경하고 적당한 시간을 투자하니 읽지 못하는 네 자리 수가 10개 이하인 표들을 금방 얻을 수 있었다.

이러한 표들을 시작으로 하여 원래의 metric으로 아이디어 4를 진행하였다.

구체적으로는 이때 꽤 다양한 시도를 했다. 기존 metric과 보조 점수 metric을 번갈아 사용하며 두 metric의 점수가 밸런스 있게 증가할 수 있게 하는 등 코드를 이래 저래 변경하였다.

그 결과 점수가 비약적으로 상승하였고, 얼마 지나지 않아 성공의 기준 점수인 8140점을 초과하는 표도 찾게 되었다.

아이디어 6: 숫자 swap

문제를 해결하는 데는 성공했지만 더 높은 점수를 얻고 싶었다. 그래서 구글링을 하였고, 나쁘지 않은 표에 대해 같은 숫자들을 단순히 서로 swap하는 것만으로도 점수를 높일 수 있다는 사실을 깨닫게 되었다. 예를 들어, 표에 있는 모든 1을 2로 바꾸고, 모든 2를 1로 바꾸는 식으로 말이다. 이런 방식은 단순하게는 총 10!개의 조합을 분석해야 하지만 조금 머리를 쓰면 그보다 훨씬 적은 개수의 조합만 비교함으로써 더 높은 점수를 얻을 수 있다고 한다. (나는 머리 안 써서 이 부분을 구현은 못하지만 느낌은 온다)

덕분에 몇 백 점 더 높은 표를 얻었고 8898점까지 획득하고 문제 풀이를 그만하였다.