[BOJ 24553] 팰린드롬 게임

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

24553번: 팰린드롬 게임

 

오늘 (24년 1월 16일) 영어 스터디에서 풀었던 문제

 

게임이론은 늘 어렵다. 그래서 optimal 한 게 뭔데?

 

처음 나온 솔루션은 dp 테이블을 만들어서 dp[n][k] (k = 0, 1)을 돌이 n개 남았을 때 k가 이길 수 있는지를 binary 하게 저장하는 거였다.

그리고 이건 모든 dp[n - (palindrome smaller than n)][!k]를 and operation으로 연산한 것으로 결정된다.

 

원래는 ‘음 그렇지 그렇게 할 수 있을 거 같아. 시간 복잡도는 얼마지?’를 물어보고

‘근데 조금 더 optimal한 솔루션이 있지 않을까?’ 이렇게 진행했었는데,

최근에는 방식을 바꿔서 하나의 솔루션이 나오면 그걸로 일단 한 번 코드를 짜보기로 했다.

 

그래서 코드를 짜기 시작했는데

n보다 작은 모든 palindrome을 구하다가 끝났다. ㅋㅋㅋ

이때 이야기한 방식이 맞는지 아직 검증이 안 됐다. 나중에 확인해봐야겠음.

 

그리고 끝나고 나서 한국어로 마무리 하는 시간에 풀이를 들었다.

1) 1-digit number는 항상 palindrome이다 -> 1~9개가 남는 상태가 되면 그때는 모두 가져갈 수 있어서 게임에서 이긴다.

2) 0으로 끝나는 palindrome은 없다 -> 10의 배수개만큼 남으면 절대로 그것을 한 번에 다 가져감으로써 이기는 방법이 없다.

 

따라서 처음으로 10의 배수개만큼 남기는 사람이 이긴다.

그러므로 주어진 n이 10의 배수가 아니면 이길 수 있다.

 

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc; cin >> tc;
    while (tc--) {
        ll n; cin >> n;
        cout << (int)(!(n % 10)) << kEndl;
    }
    
}

 

키야… 한 줄로 풀림

 

아 아무튼 n 이하의 모든 palindrome을 구하는 방법을 논한 것도 재밌었다. ㅎㅅㅎ

 

 

 

 

 

 

https://blog.naver.com/mini_gb/223324723041

[BOJ 24553] 팰린드롬 게임