[Python] 1679. 숫자놀이

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

1679번: 숫자놀이

접근법

• dp로 숫자를 만드는데 사용하는 num_list 내 숫자의 개수를 세고자 함.
  • 숫자 자체가 num_list에 있는 경우 : 1개의 숫자가 필요
  • 숫자 자체가 num_list에 없는 경우 → 2개 이상의 수로 조합되는 경우 : 각 숫자들을 만드는 데 사용된 숫자들의 합 개수만큼 필요
    ex) num_list = [1,3]일 때 -> arr[1] = 1, arr[3] = 1
    숫자 2를 만드는 데에는 1+1이 필요. 즉 2개의 숫자가 필요 -> arr[2] = 2
    숫자 4를 만드는 경우의 수는 1+3 혹은 2+2가 필요. -> arr[4] =  min(arr[1]+[3], arr[2]+arr[2], INF)
    
    

import sys


def input_func():
    N = int(input())
    num_list = list(map(int, input().split()))
    K = int(input())
    return K, sorted(num_list)


def solution(K, num_list):
    inf = sys.maxsize # min으로 값을 업데이트 하기 때문에 maxsize로 배열 초기화
    arr = [inf for _ in range(num_list[-1] * K + 2)]
    arr[1] = 1

    for i in range(1, num_list[-1]*K + 2):
        if i in num_list:
            arr[i] = 1
        else:
            # 두 가지 이상의 수로x 조합되는 경우
            # -> 조건문의 범위가 i//2 + 1이 된다.
            for j in range(1, i//2 + 1):
                arr[i] = min(arr[i], arr[j] + arr[i-j])
        if arr[i] > K:
            if i%2 == 0:
                name = "holsoon"
            else:
                name = "jjaksoon"
            print(f"{name} win at {i}")
            break



def main():
    K, num_list = input_func()
    solution(K, num_list)


if __name__ == '__main__':
    main()

---

사용된 알고리즘

다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색