[99클럽 코테 스터디] 10일차 TIL - 동적계획법, Divisor Game

[10일차] 동적계획법

 

문제: https://leetcode.com/problems/divisor-game/description/

* 대충 번역: Alice와 Bob이 차례대로 게임을 한다. Alice가 시작한다. Alice가 게임에서 이기면 true를 반환하라.

처음에는 칠판에 숫자 n이 있다. 각 사람의 순서에 다음을 포함하는 이동을 한다. "0 < x < n 이고 n % x == 0인 x를 고른다." , "숫자 n을 n-x 로 바꿔 적는다.". 플레이어가 더 이상 이동을 하지 못하면, 게임에서 진다.

Solution

해당 문제는 매 순서마다 주어진 숫자 n에 대한 가장 큰 약수를 찾는 것이다. 

약수는 쌍으로 이루어져서 n // 2 까지만 확인해도 된다. 예를 들어, n = 12 일 때 약수 쌍은 (1, 12), (2, 6), (3, 4)이기 때문이다.

동적계획법으로 해결할 수 있다.

 

1. 테이블 정의하기

d[i] = 숫자 i가 주어졌을 때 Alice가 이길 수 있는지 여부

 

2. 점화식 설정

 

3. 초기값 설정

검사하지 않은 수에 대해 false이므로, 모든 값을 false로 초기화 해준다.

class Solution(object):
    def divisorGame(self, n):
        """
        :type n: int
        :rtype: bool
        """
        dp = [False] * (n + 1)
        
        for i in range(2, n + 1):
            for j in range(1, i // 2 + 1):
                if i % j == 0 and not dp[i - j]:
                    dp[i] = True
                    break
        
        return dp[n]

Another Solution

class Solution(object):
    def divisorGame(self, n):
        return n % 2 == 0