동전1 2293

import sys
sys.stdin = open('input.txt','r')

t,m = map(int,input().split())
a = [int(input()) for _ in range(t)]
d = [0] * (m+1)
d[0] = 1

for i in range(t):
    for j in range(m+1):
        if((j-a[i])>=0):
            d[j] += d[j-a[i]]

print(d[m])

동전2 2294

import sys
sys.stdin = open('input.txt','r')

t,m = map(int,input().split())
a = [int(input()) for _ in range(t)]
d = [-1] * (m+1)

d[0] = 0
for i in range(t):
    for j in range(m+1):
        if((j-a[i])>=0 and d[j-a[i]]!=-1):
            if(d[j] == -1 or d[j]>d[j-a[i]]+1):
                d[j] = d[j-a[i]]+1

print(d[m])

크리보드 11058

import sys
sys.stdin = open('input.txt','r')

t = int(input())
d=[0]*(t+1)
d[1] = 1

for i in range(2,t+1):
    d[i] = d[i-1]+1
    for j in range(1,i-2):
        d[i] = max(d[i],d[i-(2+j)]*(j+1))

print(d[t])