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))

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