Solved problems

BOJ 16876 재미있는 숫자 게임

coloredrabbit 2020. 5. 28. 16:56

* BOJ 16876 재미있는 숫자 게임

[분류 : 다이나믹 프로그래밍]


[풀이]

  턴 수의 홀짝 여부를 따져서 누가 게임을 끝내는지 쉽게 알 수 있다. 따라서 기저 조건에 게임이 종료될 때 누가 이기는지 결정한다.

  서로 이기려고 최선을 다한다는 조건이 있기 때문에 어느 턴(p)에 어떤 수(d)로 주어지는 경우에 수행할 수 있는 행동은 1~10^3자리 숫자를 1 증가하는 4개밖에 없으므로 for문 한 번 구성해서 돌려주면 된다.

  9에서 다시 0으로 간다는 조건만 잘 구현하면 어렵지 않게 AC를 받을 수 있는 문제다.