BaaaaaaaarkingDog
코딩, 해킹
[BOJ] 9658번: 돌 게임 4

https://www.acmicpc.net/problem/9658


돌이 i개 있을 때 선수가 이기면 $D[i]=1$, 그렇지 않다면 $D[i]=0$ 이라고 합시다. 이 때


$D[0] = 1, D[1] = 0, D[2] = 1, D[3] = 0$ 임은 자명합니다. 이후의 값에 대해서는,


$D[i]$를 구하기 위해서 $D[i-1], D[i-3], D[i-4]$를 생각해야 합니다. 만약 이 셋중 어느 하나라도 값이 0이라면 돌이 $i$개일 때 선수가 이길 수 있습니다. 예를 들어 $D[i-1] = 0$인 경우, 선수가 $i$개의 돌 중 1개를 가져가면 후수는 돌이 $i-1$개인 게임의 선수와 같은 입장이고 이 때 후수는 패배하기 때문입니다. 이 성질을 바탕으로 Dynamic Programming을 하면 됩니다.


https://github.com/blisstoner/BOJ/blob/master/9658.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 2169번: 로봇 조종하기  (0) 2018.01.07
[BOJ] 5582번: 공통 부분 문자열  (0) 2018.01.07
[BOJ] 2665번: 미로만들기  (0) 2018.01.07
[BOJ] 9658번: 돌 게임 4  (6) 2018.01.07
[BOJ] 3055번: 탈출  (0) 2018.01.07
[BOJ] 9009번: 피보나치  (0) 2018.01.07
[BOJ] 10163번: 색종이  (0) 2018.01.07
  Comments
  • zagabi
    저도 그냥 i - 1, i - 3 부분을 생각하고 상근이를 기준으로 풀었는데 i - 4번째가 도무지 이해가 안가서 질문드립니다.
    제가 생각한 방식은 식은 i번째를 기준으로 만약 i - 1, i - 3, i - 4번째의 창영이가 한번이라도 이기는 경우가 발생하면 i번째는 상근이가 이기는 수가 된다.
    i - 1번째에 창영이가 이겼다. 즉, 상근이가 i - 1번째를 먹는 순간이다. 그렇다면 i번째에는 1개밖에 남지 않게 되고 창영이가 먹게 되고 자연스레 상근이가 이기게 된다.
    i - 3번째에 창영이가 이겼다. 즉, 상근이가 i - 3번째를 먹는 순간이다. 그렇다면 i번째에는 3개가 남았고 창영이가 3개를 먹던가 1개를 먹어도 자연스레 상근이가 이기게 된다.
    i - 4번째에 창영이가 이겼다. 즉, 상근이가 i - 4번째를 먹는 순간이다. 그렇다면 i번째에는 4개가 남았다. 창영이가 3개를 먹으면 상근이가 마지막 1개를 먹게 된다. 창영이가 1개를 먹으면 상근이는 1개를 먹고 창영이가 다시 1개를 먹고 상근이가 1개를 먹게 되서 상근이가 지고 창영이가 다시 이기게 된다?
    이렇게 했는데 i - 4번째에 창영이가 이기는 경우는 상근이가 무조건 지지 않나요?
  • zagabi
    정말 빠른 답변 감사합니다. 고민하느라 시간이 좀 걸렸는데요 ㅎㅎ 그니까 i - 4이라는 것이 4개를 가져간다, i - 3일때는 3개를 가져간다 라는 것을 default로 깔아놓고 DP를 만든다 이말씀이신거군요. ㅎㅎ 저는 그 상태에서 최선의 수라고 생각해서 i - 3번째 일 때 1을 가져가는 경우, 3을 가져가는 경우 다 생각해도 상근이가 이긴다. 하지만 i - 4번째의 경우 창영이가 4가 아닌 1, 3을 가져가면 상근이가 진다. 라고 생각해서 그런것 같은데요. 이런것은 dp로 특정행위를 정해놓고 해야 하는건가요? 각자 최선을 다한다고 생각하니까 헷갈리네요.. ㅠ 그리고 다시한번 감사합니다. 바킹독님! 언제한번 티모로 롤하는거 보고싶네요 하하
    • 음 현재 "나"의 입장에서는 1개/3개/4개를 가져가는 방법 중에서 이기는 수가 하나라도 있으면 되는 거잖아요. 그러니 D[i-4] = 0이면 나는 4개를 가져가는게 좋은거구요. 언제 한번 듀오 조집시닼ㅋㅋ
    • zagabi
      조지시죠ㅋㅋㅋㅋ 샹 레알입니다.
      친추부탁드려요ㅋㅋㅋ 친절한 설명 감사합니다 ㅎㅎ
댓글 쓰기