[Python][백준 15989번] 123더하기4

# https://www.acmicpc.net/problem/15989

'''

합을 이루고 있는 수의,

순서만 다른 것은, 같은 것으로 한다 ==> '1개'

즉, 다른 말로 하면

'구성은 같지만, 순서는 다르다'

'구성은 같다?'

- 사용한 1,2,3 의 개수가 같다.는 것을 의미한다

그렇다면 '중복없이 센다'는 것은 어떠한 것을 의미할까 ?

- "원하는 순서로 되어있는 합"만 구하는 것이다

- 각각의 구성에서 "대표"를 만들어보는 것이다

- ex) 1+1+2, 1+2+1, 2+1+1 --> 1+1+2 를 대표로 삼는다

- '대표'를 삼는 다양한 방법이 있지만, 그중에서 '오름차순'도 가능하다

- 이 경우, 1->2->3 순서로 이루어진 '대표'를 세는 것과 같다

- 반대로 말하면, 특정 숫자를 1,2,3 이라는 숫자로 만들때

- 1) 1로 만들고/ 2) 그 결과에 더해, 2로 만들고 / 3) 또 그 결과에 더해, 3으로 만들어보는 과정을 반복하는 것이다

'''

# 1,2,3 더하기 코드

'''

n = int(input())

m = 3

nums = [1, 2, 3]

dp = [0]*11

dp[0] = 1

for i in range(1,len(dp)):

    for j in range(m):

        if i - nums[j] >= 0:

            dp[i] += dp[i-nums[j]]

위의 코드가

바로

1,2,3 더하기 코드이다.

d[i]라는 값을 채우기 위해서,

마지막에 오는 수가

1인지,2인지,3인지가 매우 중요하게 여겨졌었다.

하지만, 1,2,3 더하기4 라는 문제에서는

매우 다른 방식으로 접근해야 한다

"사용할 수 있는 수 ex)1,2,3"가 기준이 되어야 한다

그래서, 단순히 아래와 같이

이중 for문 순서만 바꿔주면 된다

'''

n = int(input())

m = 3

nums = [1, 2, 3]  # 대표.를 '오름차순'으로 정하기 위해 이와 같이 세팅했다

dp = [0]*11

dp[0] = 1

for j in range(m):

    for i in range(1, len(dp)):

        if i - nums[j] >= 0:

            # 왜 dp[i-nums[j]]를 해주는 것일까? i-nums[j]를 만들어주기 위해

            # 사용한 모든,조합 각각에다가,

            # ex) 3 이라는 숫자를 더하여 만들어줄 것이기 때문이다

            # 계속, unique 한 조합의 경우의 수만을 dp[i]에 넣어오게 된다

            dp[i] += dp[i-nums[j]]