BOJ(123더하기(4))(15989)

작성일 | In

1,2,3 더하기(4) (15989)

  • 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.
  • 2+1+1 (1+1+2,1+2+1)
  • 이럴 때는 수를 그룹 지어서 합이 만들어진다고 생각하면 된다.
  • 모든 1이 등장하고, 모든 2가 등장하고, 모든 3이 등장했다. 이것이 유일하다고 생각하면 같은게 없어지게 된다.
  • 1로 먼저 모든 합을 만들고, 거기서 2를 추가해서 만들어보고, 거기서 3을 추가해서 만들어보는 것이다.

1,2,3 더하기

n = 4
m = 3
nums = [1, 2, 3]
d = [1]+[0]*10
for i in range(1, n+1):
    for j in range(m):
        if i - nums[j] >= 0: # d[i] = d[i-1]+d[i-2]+d[i-3]
            d[i] += d[i-nums[j]]
print(d)

1,2,3 더하기 4

n = 4
m = 3
nums = [1, 2, 3]
d = [1]+[0]*10
for j in range(m): # 중복을 제거하는 코드
    for i in range(n):
        if i - nums[j] >= 0:
            d[i] += d[i-nums[j]]
print(d)

t = int(input())
nums = [1, 2, 3]

while t:
    t -= 1
    n = int(input())
    m = 3
    d = [1]+[0]*n
    for j in range(m):
        for i in range(1, n+1):
            if i - nums[j] >= 0:
                d[i] += d[i-nums[j]]
    print(d[n])

좋은 답안

limit = 10000
d = [0] * (limit + 1)
d[0] = 1
for i in range(1, limit+1):
    if i-1 >= 0:
        d[i] += d[i-1]
for i in range(1, limit+1):
    if i-2 >= 0:
        d[i] += d[i-2]
for i in range(1, limit+1):
    if i-3 >= 0:
        d[i] += d[i-3]
t = int(input())
for _ in range(t):
    n = int(input())
    print(d[n])

또 다른 방법

dp = [[0 for _ in range(10001)] for _ in range(2)]
dp[0][2] = 1

for i in range(3, 10001):
    dp[0][i] = dp[0][i - 2] + 1
    dp[1][i] = dp[0][i - 3] + dp[1][i - 3] + 1

for _ in range(int(input())):
    n = int(input())
    print(1 + dp[0][n] +dp[1][n])

참고자료 codeplus

0%