일단 제 소스입니다. (정답자에 한해 공개 설정)

https://www.acmicpc.net/source/602293

구슬의 갯수가 16개에, 각 보드판의 상태는 3가지임에서 착안해, 32비트 정수에 2비트씩 할당하여 보드판의 상태를 표현했습니다.

그리고 골아픈 비트연산으로 보드판의 이동, 추가를 구현해서 코드가 좀 너저분합니다(..)

어쨌든 코드의 요는, i개의 명령을 실행한 상태의 보드판(board)과, 그 상태에서 나머지 명령을 실행했을 때 주어진 보드판과 같을 확률(p)를 저장하는 std::map<unsigned int, double>의 16개짜리 배열을 만들어서 메모이제이션 했다는 점입니다.

일단 정답은 나왔지만 훨씬 빠른 수행 시간을 보여준 코드들이 있어서 해당 코드들의 알고리즘이 매우 궁금합니다ㅠㅠ 군대에서 할 짓 없을 때 간간히 깨작인 코드들 대충 엮어서 만든 거라 끕..

아무튼 다르게 접근하는 방향이나, 최적화 방법 제안해 주실 수 있을까요??

++

주석을 좀 불친절하게 단 부분이 좀 있는 것 같아서 추가합니다.

77번째 줄의 if문은 T, B, L, R의 아스키 코드값은 모두 짝수, W, G의 아스키 코드값은 모두 홀수임에 착안해, T, B, L, R을 걸러내기 위한 if문입니다.

또한 78번째 줄의 수식은 {T, B, L, R}을 바로 {0, 1, 2, 3}으로 대응시키기 위해 작성한 수식입니다.

그리고 cbw 함수 내의 변수 t는 처음에는 10, 11, 12, 13, 18, 19, 20, 21번 비트에서의 1의 갯수를 gcc 혹은 VS의 내장 함수를 이용해 세어 저장합니다. 이 비트들은 보드판에서의 중간 네 칸에 해당합니다. t의 값을 이용해 중앙의 구슬이 0~3개일 경우를 각각 처리하고, 마지막엔 0으로 초기화를 시킨 후 가장자리 칸 중 구슬이 없는 칸이 몇 칸인지를 저장하는 변수로 재활용합니다.