bright

n,m = map(int,input().split()) # n : 열 m : 행

candy = []
for i in range(n):
  candy.append(list(map(int,input().split())))

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

for i in range(n):
  for j in range(m):

    a = i -1
    b = j -1

    tmp = [0] 

    if a >= 0 : 
      tmp.append( dp[a][j] )
    if b >=0 :
      tmp.append( dp[i][b] )
    if a >= 0 and b >=0 : 
      tmp.append( dp[a][b] )
    
    dp[i][j] = candy[i][j] + max(tmp)

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

dp 에 각 칸에서 가질 수 있는 최대 사탕의 수를 입력한다. 

문제에서 움직일 수 있는 경로가 3개 밖에 없으므로 간단하게 구현할 수 있다. 

점화식 : 현재 칸에서의 사탕의 최대 수 :  ( 이동 전 칸이 될 수 있는 곳들 중 사탕의 최대 수 ) + 현재 칸의 사탕 수 

k = int(input())  # 1<= k <= 45 

# A-> B  B -> BA 
a ,b = [0]*(k+1), [0]*(k+1) 
a[0], b[0] = 1,0 

for i in range(1,k+1):
  if i == 1 : 
    a[1] = 0
    b[1] = 1 
    continue 

  a[i] = b[i-1]
  b[i] = a[i-1] + b[i-1]

print (a[k],b[k])​

# 다이나믹으로 풀면... 

k = int(input())  # 1<= k <= 45 

# A-> B  B -> BA 
a ,b = 1, 0 

for i in range(k):
  if i == 0 : 
    a = 0
    b = 1 
    continue 

  tmp = a 
  a = b 
  b = tmp + b 

print (a,b)

# 왜 다이나믹..? 

# 시간 초과  ( 완전 탐색 ) 

n , m= map(int, input().split())

data=[]
for i in range(n):
  data.append( list(map(int,input().split())) )

xy = []
for i in range(m):
  xy.append(list(map(int,input().split())))

def cal( xy ):
  
  s = 0 
  for i in range(xy[0]-1,xy[2]):
    for j in range(xy[1]-1,xy[3]):
      s += data[i][j]

  print (s)

for i in range(m):
  cal(xy[i])
  

# 정답 ( 다이나믹 ) 

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