99클럽 코테 스터디 9일차 TIL - 다이나믹 프로그래밍

오늘의 학습 키워드

다이나믹 프로그래밍 (=동적프로그래밍)

오늘 공부한 내용

패턴 찾기

오늘의 회고

오늘은 문제의 패턴을 찾을려고 노력했다.

문제를 보고 이해하는데 시간이 조금 걸렸다.

해당 문제는 엘리스가 이기면 True 지면 False를 리턴하는 문제였다.

게임은 엘리스가 먼저 시작하며, 엘리스와 밥은 자신이 선택한 x만큼 움직일 수 있다. 단, 아래와 같은 조건이 있다.

0 < x < n and x % 2 == 0

또한 누군가 x만큼 움직이면 n - x 만큼 n의 숫자가 줄어든다.

가장 중요한 조건 중 하나는 엘리스와 밥은 항상 최선의 선택을 한다는 것이였다.

패턴을 찾기 위해 아래 이미지와 같이 트리구조로 엘리스가 이길때와 질때를 따져보았다.

패턴을 보니 n이 짝수일 때에는 엘리스가 이기고, 홀수일때에는 밥이 이기는 패턴을 찾아내었다.

또한 반복적으로 패턴이 보이기도 했다.

예를 들어 $f(4)$, $f(3)$ 등 여러개의 노드들이 중복된 것을 볼 수가 있었다.

n = 4일때

엘리스가 이김

n = 5일때

밥이 이김

n = 6일때

엘리스가 이김

n = 7일때

밥이 이김

동적계획법을 이용하여 풀이를 할려고 했지만 굳이 짝수일때에는 엘리스가 이기고 홀수 일때에는 밥이이기니 홀짝프로그램처럼 코드를 작성했다.

결과는 통과였다.

너무 간단하기는 했다. 그래서 코드 리팩토링을 하니 아래 이미지와 같은 결과가 도출되었다.

def solution(n:int) -> bool:
  return n % 2 == 0

두번째로 통과하였다.

오늘은 문제가 일정한 패턴을 찾으면 쉽게 풀리는 경우였다.

하지만 문제가 쉽다고해서 자만하지는 않아야겠다!

내일 더 정진해서 패턴을 찾아보고 차분히 여러가지 방향을 찾아 풀 수 있도록 노력해야겠다.

결과물

문제내용

엘리스와 밥은 게임을 한다.

게임은 엘리스가 먼저 시작하며, 엘리스와 밥은 자신이 선택한 x만큼 움직일 수 있다. 단, 아래와 같은 조건이 있다.

• 0 < x < n and x % 2 == 0

x만큼 움직이면 n - x 만큼 n의 숫자가 줄어든다.

단, 엘리스와 밥은 최선의 선택만을 한다.

예시

n = 3

엘리스먼저 1칸을 움직이고, 밥이 1칸을 움직여서 엘리스는 다음칸을 움직일 수 없게됨 따라서, 엘리스의 패배

엘리스가 패배하면 False를 이긴다면 True를 리턴하라

풀이방법

아래 이미지와 같이 n의 경우를 트리구조로 만들어보았다.

n = 4일때

엘리스가 이김

n = 5일때

밥이 이김

n = 6일때

엘리스가 이김

n = 7일때

밥이 이김

이런 패턴을 생각할 때 n이 1부터 7까지 엘리스와 밥이 돌아가며 이긴다는 패턴이 보였다.

따라서 짝수일 때에는 엘리스가 이기고, 홀수 일때는 밥이 이긴다.

# 첫번째 풀이
class Solution:
    def divisorGame(self, n: int) -> bool:
        if n % 2 == 0:
            return True
        else:
            return False

# 두번째 풀이
class Solution:
    def divisorGame(self, n: int) -> bool:
        return n % 2 == 0