[boj1679] 숫자놀이. DFS, DP, itertools 모두 학습이 가능한 문제

Jonas M·2021년 8월 26일

Coding Test

목록 보기

32/33

boj1679 숫자놀이 백준 1679
DFS와 DP, itertools로 직접 구현을 모두 해볼 수 있는 문제이면서, 의외로 itertools로 풀었을 때가 DFS보다 더 효율적이었던 문제

Question

nums array와 최대 개수를 주면, nums의 숫자들을 최대 개수 한도에서 아무거나 뽑아서 그 합을 만들 수 있다. 그리고 1부터 숫자를 올려가면서 못 만드는 숫자가 처음 나오면 return.
[1,2]와 2개가 주어진다면 1, 2, 3, 4(2+2)까지 만들 수 있고 답은 5가 되는 것이다. 숫자가 좀 길어지면 중간중간 빈 숫자들이 발생하게 된다.

Solution

우선 공통적으로 memo list를 만들어서 (길이는 max값 * 최대 개수: 만들 수 있는 가장 큰 수) 가능한 숫자들을 True, 불가능하면 False로 할당해준다. 마지막에 1부터 1씩 올라가면서 False를 발견하면 return.

# idx 1이 그대로 숫자 1을 나타낼 수 있도록 앞에 False를 하나 더 붙여줬음
memo = [False for _ in range((nums[-1]*max_num) + 1)]

Solution 1: itertools product

itertools.product는 주어진 iterable 자료 안에서 중복/순서 관계 없이 n번 원소를 추출하는 함수이다.
숫자가 3개 주어지고 최대 5개를 활용할 수 있다면 (0,0,1), (1,2,2), (2,1,1) 등의 각 숫자별 개수 pair를 만들어야 한다. (1,2,2)는 숫자A가 1번, 숫자B가 2번, 숫자C가 2번 포함된 수.
그렇다면 [1,2,3,4,5]에서 중복/순서 관계 없이 3개의 숫자를 뽑으면 되는 것이다. 그리고 (3,4,5)와 같은 경우들은 합이 5가 넘어가므로 불가능하기 때문에 filter로 제거해준다.

pool = list(filter(lambda x: 0<sum(x)<=max_num, list(product(pool, repeat=length))))

pair들을 loop 돌면서 가능한 경우들을 memo에서 제거해주면 된다.
코드는 아래 깃헙에.

Solution 2: DFS

한 step에서 +3, +5로 갈 수 있는 DFS를 돌리면 된다. 주의할 점은 꼭 5개가 되어야만 하는 게 아니기 때문에 매 step 마다 memo를 업데이트해주는 것.

def dfs_helper(cum, length):
	nonlocal nums, max_num, memo
    	memo[cum] = True
        if length == max_num: return

        for num in nums:
            dfs_helper(cum + num, length+1)
    
dfs_helper(0, 0)

시간 초과가 나왔다. itertools는 되는데 이게 시간초과가 나오는 이유는 최대 개수가 커질 때이다. (dfs를 돌아야할 깊이가 깊어질수록) 경우의 수가 급수로 늘어나기 때문이다. (결과는 아래에)

Solution 3: Dynamic Programing

DFS와 유사한 개념이면서 중복 탐색을 줄일 수 있는 방법이다.
dp[i]는 숫자를 i번 골랐을 때 가능한 합들
dp[i+1]은 dp[i]에 각각의 nums를 더해줬을 때 나오는 수들이 되어야 한다.
DFS와 달리 DP에서는 중간 단계들에서 중복되는 수들을 없애줄 수 있다. 그래서 다음 단계로 넘어갈 때 같은 숫자를 탐색하게 되는 경우가 사라지게 된다.
예를 들어, i번째에서 3을 만들 수 있는 경우가 3가지가 있다면, DFS는 그 세 가지 경우에서 모두 i+1번째로 가면서 nums의 숫자들을 더해주게 되지만, DP는 합이 3인 경우엔 하나로 취급하여 셋중 한 가지 경우만 추가로 탐색을 이어간다고 생각할 수 있다.

    for i in range(2, len(dp)):
        before = dp[i-1]
        for b in before:
            for num in nums:
                memo[b+num] = True
                dp[i].add(b+num)