백준 - 돌 게임 유형

유형: dp

문제 리스트: https://solved.ac/search?query=돌 게임 

solved.ac - 검색

 

돌 게임 문제는 조금씩 변형해서 여러 문제가 있다.

1, 3개씩 가져가는 경우, 4개씩도 가져가는 경우, 마지막으로 가져간 사람의 승패를 반대로 하는 경우가 주로 있다.

문제 자체도 다소 추상적이라 감을 잡기 쉽지 않지만, 이런 문제는 규칙만 알면 O(1)로도 풀 수 있다.

 

몇달 전에 풀긴 했지만, 나는 1, 3개씩 가져가는 경우에서 규칙을 찾았었다.

개수를 2로 만들면 1밖에 못가져가기에 무조건 2로 만든 사람이 이긴다. 이걸 활용했던 것 같다.

패턴을 파악하기 위해 1부터 시작해서 경우의 수를 그려나갔다. 6~7정도가 되면 패턴이 보인다.

 

1, 3, 4개씩 가져가는 경우는?

1, 3은 규칙을 찾았지만 이 경우는 찾지 못하고 포기했었다.

경우의 수를 그리면 패턴이 보이긴 했지만, 모든 패턴을 파악하진 못했다.

그러다 이 글을 봤다. https://evaporation.tistory.com/9

백준(BOJ) 9660 : 돌 게임 6

이 글을 보면 1, 3, 4개씩의 경우는 어떤 패턴을 보이는지 알 수 있다.

패턴을 파악하는 과정은, 우선 배열 dp로 적당한 수의 범위까지 경우의 수를 출력해본다.

그러면 패턴을 파악하기 한결 수월해진다.

패턴이 보이지 않는다면, 코드로 적당히 경우의 수를 출력해보자. 이번 교훈이다.