원글 페이지 : 바로가기
DP 문제 https://www.acmicpc.net/problem/15989 접근 방식 1, 2, 3 더하기 문제와 다른점 1, 2, 3 더하기 문제는 1, 2, 3을 활용하여, 그 합이 k가 되도록 만드는 순열 문제이다. 아래 두가지 경우는 각각 다른 경우이다. 1+2+1 2+1+1 1, 2, 3 더하기 4 문제는 1, 2, 3을 활용하여, 그 합이 k가 되도록 만드는 조합 문제이다. 아래 두가지 경우는 같은 경우이다. 1+2+1 2+1+1 동전 문제와 같은점 동전 문제는 주어진 동전의 금액을 활용하여, 그 금액의 합이 k원이 되도록 만드는 조합 문제이다. 이 문제는 1, 2, 3을 활용하여, 그 합이 k가 되도록 만드는 조합 문제이다. 따라서, 동전 문제와 같은 방법으로 문제를 풀 수 있다. 💡 풀이코드 (성공 – 2차원 배열) import sys
t = int(sys.stdin.readline())
def count_ways(n):
# DP 테이블 초기화
dp = [[0] * (n + 1) for _ in range(4)]
dp[0][0] = 1
dp[1][0] = 1
dp[2][0] = 1
dp[3][0] = 1
for i in range(1, 4):
for j in range(1 ,n + 1):
if j >= i:
dp[i][j] = dp[i][j – i] + dp[i – 1][j]
else:
dp[i][j] = dp[i – 1][j]
return dp[3][n]
for _ in range(t):
n = int(sys.stdin.readline())
print(count_ways(n)) 초기화 dp 배열을 (3 + 1) X (n + 1) 크기로 만든다. dp[i][0]을 1로 초기화해준다. 이는, 숫자 i를 이용해 0을 만드는 가짓수가 1개임을 의미한다. 1을 이용해 합 0을 만드는 가짓수 = 1 (1을 사용 안하는 가짓수 1가지) 2을 이용해 합 0을 만드는 가짓수 = 1 3을 이용해 합 0을 만드는 가짓수 = 1 dp = [[0] * (n + 1) for _ in range(4)]
dp[0][0] = 1
dp[1][0] = 1
dp[2][0] = 1
dp[3][0] = 1 점화식 dp[i][j] = dp[i][j – i] + dp[i – 1][j] = i개의 수를 사용하여 합이 j인 수를 만드는 가짓수 = i개의 수를 사용하여 합이 j-i인 수를 만드는 가짓수(1, 2, 3을 무한정 사용 가능하므로) + i – 1개의 수를 사용하여 합이 j인 수를 만드는 가짓수 = i번째 수를 적어도 하나 사용하는 가짓수 + i번째 수를 사용하지 않는 가짓수 dp[i][j] = dp[i][j – i] + dp[i – 1][j] 💡 풀이코드 (성공 – 1차원 배열) import sys
t = int(sys.stdin.readline())
def sol(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, 4):
for j in range(1, n + 1):
if j – i >= 0:
dp[j] += dp[j – i]
return dp[n]
for _ in range(t):
n = int(sys.stdin.readline())
print(sol(n)) 초기화 dp 배열을 만들고, dp[0]을 1로 초기화해준다. 이는, 숫자 i개(1, 2, 3)를 이용해 0을 만드는 가짓수가 1개임을 의미한다. dp = [0] * (n + 1)
dp[0] = 1 점화식 dp[j] += dp[j – i] = i개의 수를 사용하여 합이 j인 수를 만드는 가짓수 = j를 만들기 위해 마지막에 숫자 i를 더했다고 가정할 때, 그 이전에 j – i를 만드는 방법의 수를 더해주는 방식 for i in range(1, 4):
for j in range(1, n + 1):
if j – i >= 0:
dp[j] += dp[j – i] 순열 VS 조합 1) 순열 코드 import sys
t = int(sys.stdin.readline())
def sol(n):
dp = [0 for _ in range(n + 1)]
dp[0] = 1
for i in range(1, n + 1):
for j in range(1, 4):
if i – j >= 0:
dp[i] += dp[i – j]
print(dp[n])
for _ in range(t):
n = int(sys.stdin.readline())
sol(n) 2) 조합 코드 (풀이코드) import sys
t = int(sys.stdin.readline())
def sol(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, 4):
for j in range(1, n + 1):
if j – i >= 0:
dp[j] += dp[j – i]
return dp[n]
for _ in range(t):
n = int(sys.stdin.readline())
print(sol(n)) 차이점 차이점은 바로 이중 for문에 있다. 1번 코드에서는 합이 i 되는 경우의 수를 구하기 위해 두번째 for문을 돌며 j (1, 2, 3)을 차례대로 계산한다. 이 방식은 i에 대해 동시에 1, 2, 3을 사용해 계산하는 방식이다. 즉, 특정 합이 되 ㄹ수 있는 모든 경우의 수가 한 번에 고려된다. 중복된 경우의 수가 포함되는 순열이다. 2번 코드에서는 i (1, 2, 3)을 각각 이용하여 두번째 for문을 돌며 합이 j 되는 경우의 수를 계산한다. 즉, 1을 사용해서 경우의 수를 먼저 구한 다음, 2를 사용해서 그 위에 더 가능한 경우의 수를 계산하고, 마지막으로 3을 사용해서 그 위에 더 가능한 경우의 수를 계산하는 방식입니다. 이 경우 작은 숫자부터 순차적으로 누적해 가는 형태이다. 다시 말해, 각 숫자에 대한 영향을 순차적으로 반영해가는 방식이다. 작은 숫자의 경우의 수가 먼저 계산되고, 그 뒤에 더 큰 숫자들의 조합이 추가된다. 중복된 경우의 수가 방지되는 조합이다. 참고문헌 https://velog.io/@dhelee/%EB%B0%B1%EC%A4%80-15989%EB%B2%88-123-%EB%8D%94%ED%95%98%EA%B8%B0-4-Python-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8DDP [백준] 15989번: 1,2,3 더하기 4 / Python / 다이나믹 프로그래밍(DP) 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. velog.io