99클럽 코테 스터디 20일차 TIL + 재귀호출, 메모이제이션, [leetcode] Divisor Game

✨ 문제 

Divisor Game

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number n on the chalkboard. On each player's turn, that player makes a move consisting of:

• Choosing any x with 0 < x < n and n % x == 0.
• Replacing the number n on the chalkboard with n - x.

Also, if a player cannot make a move, they lose the game.

Return true if and only if Alice wins the game, assuming both players play optimally.

 

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

 

 

 

✨ 개념

동적 프로그래밍 Dynamic Programming

- 복잡한 문제를 작은 문제로 분해하여 해결하는 알고리즘 기법.

- 동적 프로그래밍을 적용하기 위해서는 다음 2가지 조건이 필요하다.

최적 부분 구조 : 전체 문제의 최적해를 부분 문제의 최적해로부터  찾을 수 있어야함.

중복되는 부분 문제 : 부분 문제가 여러번 중복되어 반복계산 되어야함.

 

동적 프로그래밍의 두 가지 접근 방식

상향식 접근법 Bottom-up

- 작은 하위 문제부터 해결해 나가며 차례로 큰 문제를 해결하는 방식.

- 일반적으로 반복문을 사용하여 구현됨.

 

하향식 접근법 Top-down

- 큰 문제를 해결하기 위해 재귀적으로 하위 문제를 호출하는 방식

- 하위 문제의 결과를 저장하기 위해 메모이제이션을 사용함.

 

 

✨ 최종코드

class Solution {
    public boolean divisorGame(int n) {
        boolean[] dp = new boolean[n + 1];
        dp[1] = false;
        
        for (int i = 2; i <= n; i++) {
            for (int x = 1; x < i; x++) {
                if (i % x == 0 && !dp[i - x]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
}