[백준] 1679번: 숫자놀이 풀이

사용한 기술 스택들:  

 

1679번: 숫자놀이 (acmicpc.net)

1679번: 숫자놀이

코드:

import sys

input = lambda: sys.stdin.readline().rstrip()
n = int(input())
l=list(map(int,input().split()))
nums = set(l)
k = int(input())
dp=[float('inf') for _ in range(l[-1]*k+2)]
for i in range(1,l[-1]*k+2):
    if i in nums:
        dp[i]=1
    else:
        for j in range(1,i//2+1):
            dp[i]=min(dp[i],dp[j]+dp[i-j])
    if dp[i]>k:
        s="holsoon" if i%2==0 else "jjaksoon"
        print(f"{s} win at {i}")
        break

 

 

풀이:

이 문제는 전형적인 DP문제라 할 수 있다. 이 문제를 보면, 수들을 $k$번 이하로 사용하여 1부터 계속 수들을 만들어 나가야 하는 걸 할 수 있다.

 

 

if dp[i]>k:
    s="holsoon" if i%2==0 else "jjaksoon"
    print(f"{s} win at {i}")
    break

여기서 눈치채야 할 중요한 포인트는 1부터 계속 숫자를 만들어 낼 때, $k$번 이하로는 그 수를 만들어 낼 수가 없다면, 그 수가 홀수면 짝순이의 승리, 짝수면 홀 순이의 승리라는 것을 알 수 있다.

 

 

for i in range(1,l[-1]*k+2):

이 코드의 로직은 간단하다. $l[-1]$은 최댓값이기 때문에 1부터 시작해서 수를 만들면 최대 $l[-1]\times k$ 까지가 만들 수 있는 수의 최대라는 걸 알 수가 있다. 여기서 우리는 누가 이겼는지 알아야 하기 때문에 ($k$가 초과가 나야 승자 판별을 할 수 있음) +1을 해줘서 (range는 끝이 포함이 안되기 때문에 또 +1) 이런 범위를 설정해준다.

 

 

dp=[float('inf') for _ in range(l[-1]*k+2)]
for i in range(1,l[-1]*k+2):
    if i in nums:
        dp[i]=1
    else:
        for j in range(1,i//2+1):
            dp[i]=min(dp[i],dp[j]+dp[i-j])

dp도 저 순회하는 크기만큼 설정해주고, dp[i]에는$i$라는 숫자를 만들기 위해 최소 몇 개의 주어진 숫자를 써야 하는지 저장을 해준다. dp에는 min연산이 사용되기 때문에 float('inf')로 먼저 기본값을 정해준다.

 

이제부터 2부터 최댓값까지 $i$를 순회시켜준다.

 

if i in nums:
    dp[i]=1

$i$가 이미 주어진 숫자 nums에 있으면 i를 만드는 최소 사용 비용은 1로 설정을 해준다.

 

 

for j in range(1,i//2+1):
    dp[i]=min(dp[i],dp[j]+dp[i-j])

만약에 $i$가 nums안에 없다면, 두 가지 이상의 수 조합으로 만들어 줘야 하기 때문에 여기서 생각을 해봐야 한다.

 

어차피 숫자는 1부터 순회하고 1이 항상 포함되어 있기 때문에 일단은 모든 수는 만들 수가 있다. 그렇기 때문에 문제에서 1과 3이 주어졌다면, dp[2]=2, dp[3]=1, dp[4]=2, dp[5]=3이라는 것을 알 수 있다.

 

$i$가 5라면, 수의 조합은 (1,4),(2,3) 두 가지로 만들 수 있을 것이다.

즉, min((1을 만드는 최소 비용)+(4을 만드는 최소 비용),(2을 만드는 최소 비용)+(3을 만드는 최소 비용))이다.

 

즉, 1부터 $i//2$까지 $j$를 잡고, 더하면 $i$를 만들 수 있는 $(j, i-j)$의 쌍들을 만들어서 모든 조합의 최솟값을 찾으면 된다.

이렇다면 dp에는 항상 최소만이 저장되기 때문에, 이 조합들의 합의 최소도 $i$를 만드는 최소라는 것이 보장이 된다.

 

이대로 순회하다 dp[i]가 k를 넘으면 위에서 말한 것처럼 승자를 판별해주면 된다.

 

이 문제의 최악 시간 복잡도는 $O((NK)^2)$이지만 상수가 작을 거라서 파이썬으론 최소 시간만 걸린다.

 

소스코드:

baekjoonProblems/숫자놀이.py at main · LimePencil/baekjoonProblems (github.com)

GitHub - LimePencil/baekjoonProblems: 백준 코딩문제 자바&파이썬 해답