DP복습_ 1,2,3더하기(1,4), 제곱수의 합, 동전 문제(0,1,2)

작성일 | In

1,2,3 더하기(1)

nums = [1, 2, 3]
for _ in range(int(input())):
    n = int(input())
    d = [1] + [0]*10  # d[n]은 n을 나타내는 방법의 수
    # d[n] = (마지막이 1인 경우, 마지막이 2인 경우, 마지막이 3인 경우)
    # 4를 만들 수 있는 경우가, 1에 3을 더하는 것, 2에 2를 더하는 것, 3에 1을 더하는 것
    # 5를 만들 수 있는 경우 4에 1을 더하는 것, 3에 2를 더하는 것, 2에 3을 더하는 것
    for i in range(1, n+1):
        for num in nums:
            d[i] += d[i-num]
    print(d[n])

1,2,3 더하기(4)

  • 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.
  • 1로 먼저 모든 합을 만들어보고, 2를 추가해서 모든 합을 만들어보고, 3을 추가해서 모든 합을 만든다
nums = [1, 2, 3]
for _ in range(int(input())):
    n = int(input())
    d = [1] + [0]*n
    for num in nums:
        for i in range(num, n+1):
            d[i] += d[i-num]
    print(d[n])

1699 제곱수의 합

  • 주어진 자연수 N을 제곱수들의 합으로 표현할 때에, 그 항의 최소 개수를 구하는 프로그램

  • 예를 들어 7은 2+1+1+1 이므로 4가 된다.

  • 무조건 큰 수들의 제곱으로만 나타내는 것이 답이 아니다.
  • 예를 들어 43 = 25+9+9 < 36+4+1+1+1
  • 따라서 어떻게 하면 최소의 제곱수들로 표현 할 수 있는지 고민해봐야 한다.
  • 43의 크기 내로 표현할 수 있는 제곱수들은 1,4,9,16,25,36이 있다.
  • 이 수들을 이용해 최소로 구성할 수있는 방법은 결국 43-1,43-3,43-9,43-16,43-25,43-36 이렇게 6가지 경우로 나눠서 빼가며,

  • 저 6가지 경우 중 어느 경우가 결국 최소로 만들어 주는 지를 찾아야 한다.

  • 이를 바탕으로 식을 세워보자
  • d[43]= 43을 제곱수로 나타냈을 때의 항의 최소 개수
  • d[43] = d[43-1*1], d[43-2*2], d[43-3*3],d[43-4*4],d[43-5*5],d[43-6*6] 중 최솟값 +1
  • 여기서 +1을 해주는 이유는, 제곱수 2를 가지고 예를 들어보면, 43에서 2의 제곱인 3를 빼면 d[39]가 나온다. 이는 결국 39에 2^2를 더해서 43을 만들어준다는 의미로, 39를 만드는 최소 제곱수의 항의 개수 +1이 된다.
  • 1*1로 뺀 경우는, 전부 1의 제곱들로만 나타낸다는 의미이므로, d[1]을 제외하고는 최소항이 될 수 없기 때문에, 굳이 비교해줄 필요가 없다.
  • 따라서 d 배열 생성시, d[i]=i로 초기화하여 i 번째를 전부 1의 제곱수로 표현하는 것으로 한다.
n = int(input())
dp = [0]*(n+1)
for i in range(1, n+1):
    dp[i] = i
    j = 2
    while j*j <= i:
        if dp[i] > dp[i-j*j]+1:
            dp[i] = dp[i-j*j]+1
        j += 1
print(dp)

동전 0 문제

  • 동전에는 1,5,10,50,100,500원이 있다.
  • 이 동전들로는 정수의 금액을 만들 수 있으며, 그 방법도 여러가지가 있을 수 있다.
  • 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성해보기
  • 입력 첫 줄에는 테스트 케이스의 개수, 첫 번째 줄에는 동전의 개수가 주어지며, 두 번째 줄에는 각 동전의 금액이 오름차순으로 정렬되어 주어진다.
  • 세 번째 줄에는 N가지 동전으로 만들어야 할 금액이 주어진다.
t = int(input())
for _ in range(t):
    n = int(input())
    C = list(map(int, input().split()))
    m = int(input())
    d = [1]+[0]*m
    # d[0] = 1  # d[j] += d[j-a[i]]에서 j-a[i]=0이 되는 경우가 반드시 발생하기 때문이다.
    # # 이 경우는 m과 첫 번째 동전의 금액이 같아지는 경우로 예를 들어 2원으로 2원을 만드는 경우를 의미하기에, 1번은 반드시 들어간다. 따라서 d[0]=1이 필요하다
    for coin in C:
        for m in range(coin, m+1):
            d[m] += d[m-coin]
    print(d[m])

동전 1

  • 위에서 구한 것과 똑같은 문제, 단지 범위만 커진 것일 뿐
n, m = map(int, input().split())
coins = [int(input()) for _ in range(n)]
d = [1] + [0]*m
for coin in coins:
    for m in range(coin, m+1):
        d[m] += d[m-coin]
print(d[m])

동전 2

n, m = map(int, input().split())
coins = [int(input()) for _ in range(n)]
d = [0]+[100001]*m
for coin in coins:
    for j in range(coin, m+1):  # j-a[i]>=0 조건을 range(coin,m+1)로 대체가능
        d[j] = min(d[j], d[j-coin]+1)
if d[m] == 100001: # 해당 금액을 만들 수 없다는 이야기는, d[k]번째 값이 초기값에서 변경되지 않았다는 의미.
    d[m] = -1
print(d[m])

참고자료 codeplus 제곱수의합

0%