bright

https://www.acmicpc.net/problem/12865

n, k = map(int, input().split()) # n 은 물건의 수 k 는 총 무게 

w = [0]*n 
v = [0]*n 

for i in range(n):
  w[i],v[i] = map(int,input().split())

dp = [ [0]*(k+1) for _ in range(n+1) ] 

for i in range(n+1):
  for j in range(k+1):
    if w[i-1] <= j:
      dp[i][j] = max( v[i-1]+ dp[i-1][j-w[i-1]], dp[i-1][j] )
    else:
      dp[i][j] = dp[i-1][j]

print(dp[n-1][k])

내가 헷갈렸던 것.. 

점화식 까지는 접근 했음. 

그런데, dp 의 기준을 only 무게로 잡아서,  만약 무게가 6 인 경우 3+3 이 최대가 되면 어떻게 하는지 고민을 많이 함. 

->  순차적으로 물건이랑 무게 둘 다 를 기준으로 하는 dp 를 선언하면 해결됨. 

그리고 w[i-1] > i 인 경우에 대해서 생각하지 못했음. 

못 들어가면 그 전의 값으로 초기화 해주기. 

맨날 문제가 비슷하면서도 잘 안 풀린다. 

아직 잘 모른다는 뜻인 것 같다. 

잘 설명해둔 블로그를 찾았다. 참고하기. 

# Reference 

https://dojinkimm.github.io/algorithm/2019/10/19/dp-2.html

d,k = map(int,input().split())
# d 는 넘어온 날 3<=d<=30 // k 는 d날 준 떡의 개수 10<=k<=100,000

dp = [ [0,0] for _ in range(d)] 

dp[0] = [1,0]
dp[1] = [0,1]

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

for i in range(1, k//2+1):
  if (k - dp[d-1][0]*i) % dp[d-1][1] == 0 :
    print(i)
    print((k - dp[d-1][0]*i) // dp[d-1][1])
    break

def no_reduce(n):
  dp = [ [0]*10 for _ in range(n) ] 

  dp[0] = [1]*10 

  for i in range(1,n):
  
    #dp[i][0] = dp[i-1][0] 

    for j in range(0,10):
      for k in range(j+1):
        dp[i][j] += dp[i-1][k]

  print(sum(dp[n-1]))

t = int(input())
data = [0]*t

for i in range(t):
  data[i] = int(input())

for i in data:
  no_reduce(i)

1 자리 인 경우 0~9 까지 1개씩 가능함.  -> dp[0] = [1]*10 

2 자리 이상인 경우, 

1자리 작은 경우의 수에서, 나보다 작거나 같은 수가 나오는 경우 만큼 내가 나올 수 있다. 

ex ) 

3자리 숫자 중, 숫자 2가 마지막에 오는 경우의 수 = 2자리에서 ( 0이 오는 경우의 수 + 1이 오는 경우의 수 + 2가 오는 경우의 수 ) 

n = int(input())

if n % 2 == 1 : 
  print("CY")
else : 
  print("SK")

SK  : n-1, n-3, n-5, n-7 ...

CY : n-2, n-4, n-6, n-8 ... 

내가 가져가서 돌이 0개 ( 이하 ) 가 되면 진다. 

SK 는 무조건 n 에서 홀 수 개의 돌을 뺀 만큼을 CY 에게 줄 수 있고 

이로써 CY 는 항상 짝수의 값을 받아 SK 에게 홀수 로 돌려 준다. 

( 홀수 - 홀수 = 짝수, 짝수 - 홀수 = 홀수 )   

따라서 n 이 짝수이면 SK가 이기고 ( CY 가 n-2k 해서 결국 마지막 돌을 가져감 ) 

n 이 홀수이면 CY가 이긴다. 

# 틀린 코드 

n = int(input())
data = list(map(int,input().split()))

dp = [ 0 for _ in range(n)]
dp[0] = data[0]


for i in range(n):
  max_sum = 0 
  for j in range(0,i):
    if max_sum < dp[j] and data[i]> data[j]:
      max_sum += data[j]
  dp[i] = max_sum + data[i]

print( max(dp))

# 정답 

n = int(input())
data = list(map(int,input().split()))

dp = [ x for x in data]

for i in range(n):
  for j in range(i):
    if data[i] > data[j]:
      dp[i] = max(dp[i], dp[j]+data[i])

print( max(dp))

간단하게 생각하는 연습하기... 

# 시간 초과 

n = int(input()) # 1<=n <= 100,000 

dp =[10001]*(n+1) 

dp[0]=0
sq=[0]*(n+1)

for i in range(1,n+1):
  sq[i] = i**2
  for j in range(i,n+1):
    k = j - sq[i]

    if k >=0 and dp[k] != 10001 : 
      dp[j] = min( dp[j], dp[k]+1 )

print(dp[n])

# 시간 초과 2 

n = int(input()) 
dp = [0] * (n+1) 

for i in range(1, n+1): 
  dp[i] = i

  for j in range(1, i): 
    if (j * j) > i: 
      break 
      
    dp[i] = min(dp[i], dp[i - j * j] + 1) 

print( dp[n])

# min 함수 사용 하지 말고 if 문 적용하기 

n = int(input()) 
dp = [0] * (n+1) 

for i in range(1, n+1): 
  dp[i] = i

  for j in range(1, i): 
    if (j * j) > i: 
      break 
      
    dp[i] = min(dp[i], dp[i - j * j] + 1) 

print( dp[n])

.. 뭔가 비슷하게는 푸는 것 같은데 조금씩 어긋나는 기분.. 

좀 더 생각하고 코딩하기.. 

# 틀린 코드.. 왜? 

n, k = map(int,input().split()) # n 개의 동전, k 원 

coin = [0]*n 

for i in range(n):
  coin[i] = int(input())

dp = [10001]*(k+1)
dp[0] = 1

for i in coin : 
  for j in range(i, k+1):
    if dp[j-i] != 10001 :

      if dp[j] == 10001 : 
        dp[j]= 0
      dp[j] += dp[j-i]

print(dp[k])

# 정답

n, k = map(int,input().split()) # n 개의 동전, k 원 

coin = [0]*n 

for i in range(n):
  coin[i] = int(input())

dp = [0]*(k+1)
dp[0]=1

for i in coin :
  for j in range(i, k+1):
    if j-i >= 0 : 
    # j-i 를 만드는 방법에 지금 coin 값을 더하는 식을 세울 수 있으므로. 
      dp[j] += dp[j-i]

print(dp[k])

n = int(input()) # 오르막 수 <= 1000

dp = [ [0,0,0,0,0,0,0,0,0,0] for _ in range(n)] 

for i in range(10):
  dp[0][i] = 1

for i in range(1,n):
  for j in range(10):
    for k in range(j+1):
      dp[i][j] += dp[i-1][k]
      
print( sum(dp[n-1])%10007 )

t = int(input())

n = [0]*t
m = [0]*t 
for i in range(t):
  n[i],m[i] =  map(int,input().split())

for i in range(t):
  dp = [0]* n[i]
  dp[0] = m[i]

  for j in range(1,n[i]): 
    dp[j] = dp[j-1]*(m[i]-j)//(j+1)

  print(dp[n[i]-1])

n = int(input())  # 사려는 카드의 개수 
data = [0]+list(map(int,input().split()))

# n 개를 사기 위해 가장 돈을 많이 내는 경우의 수.. 

dp = [0]*(n+1) 

dp[1] = data[1]

for i in range(2,n+1):
  for j in range(1,i+1):
    if dp[i] < dp[i-j] + data[j]:
      dp[i] = dp[i-j]+ data[j]
print(dp[n])