[일반] 돌게임6,7 <- 이거원래 뉴비들도풀수있음 ?

[익명(1.224)]

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

Baekjoon Online Judge

이제막 브론즈 100문제정도 풀고 실버 345 풀고있었는데

우연히 실버에서 돌게임 1 찾아서 풀다보니까 문제가 다 비슷한거야

게임 이론이긴한데 규칙만 찾으면 풀수있어서 ( 오히려 규칙은 찾았는데 뉴비라 이걸 어케 작성해야하지 ? 생각하고있었음 )

손가락으로 세면서 규칙찾다가 메모장에 하루죙일 써가면서 찾았음

예를들어 돌게임7은 골드2문제인데

메모장으로 써가면서보니까 1부터 10까지 승패승승패 승패승승패
10110 10110 이런형식이길래

5로 나눈 나머지가 0, 2 둘중 하나라도 만족하면 0
그거 아니면 1

이렇게 냈는데 맞다고함 (이와중에 long안쓰고 int로 냈다가 5번틀려서 왜틀렸지하고 헤멤 )
물론 이거하나 거의반나절동안 붙잡고있긴했음
이거 내가 제대로 푼거맞음 ?

[익명(115.92)]

스프라그 그런디 이론이라고 있음

[Bubbler(bubbler)]

규칙 찾는 부분까지는 제대로 푼게 맞는데, 그 규칙을 제대로 증명해보는 것도 좋을듯 돌게임7을 예로 들면 승리하는 경우: 5k+1, 5k+4: 각각 1개, 4개를 가져가서 5k를 만들수 있음 5k+3: 1개를 가져가서 5k+2를 만들수 있음 패배하는 경우: 1, 4, 16, 64,...는 전부 5로 나눠서 1 아니면 4임. 5k+0: 어떻게 가져가도 5k'+1이나 5k'+4가 남음 5k+2: 어떻게 가져가도 5k'+1이나 5k'+3이 남음 이러면 증명끝 - dc App

[노는게제일좋아(aig0016)]

그렇게 푸는 것도 맞고, 증명이 본체인 것도 맞음 실제로 전 문제에서 주어지는 변수가 N 하나밖에 없고, 문제 다 읽고 떠오르는 생각 없으면 1부터 대입들어감...