박종훈 기술블로그

(Leetcode) 377 - Combination Sum IV

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.


https://leetcode.com/problems/combination-sum-iv/

dp 문제이다.

내가 푼 방식

from typing import List


class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)

        for i in range(1, target + 1):
            for num in nums:
                if i == num:
                    dp[i] += 1
                elif i > num:
                    subtract = i - num
                    dp[i] += dp[subtract]

        return int(dp[-1])

오히려 너무 어렵게 생각해서 시간이 좀 더 걸렸다.

예시로 nums = [1,2,3], target = 4 인 상황을 생각해보자.

dp의 각 값을 그 수일 때의 조합의 수 라고 해보자

nums에 해당 값이 있을 때는 조합 없이 그 수만 사용해서 target을 구성할 수 있다. 따라서 바로 1을 추가해준다. (dp[i] += 1)

그 외의 경우에는 nums를 iterate 하면서 체크를 해보면 되는데

예를들어 dp[4]에서

여기서 포인트는 뒤에 숫자를 추가한다고 combination의 수가 증가하지는 않는다.

따라서 dp[4] = dp[4-1] + dp[4-2] + dp[4-3] = dp[3] + dp[2] + dp[1] 이 되는것이다.

categories: 스터디-알고리즘

tags: 파이썬 , 알고리즘 , python , algorithm , Leetcode , DP , combination , sum