bright

n = int(input()) # 1<=n<=1000
data= list(map(int,input().split()))

k = 0 
cnt = 0 

for i in data:
  if i == k : 
    cnt += 1 
    k = ( i + 1 ) %3 

print(cnt)

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

dp=[1]*1001

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

print ( max(dp) )

# 가장 긴 증가하는 수열 찾기랑 비슷 

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

dp = [1]*1001

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

print(max(dp))

자기 자신인 상자 1 개는 무조건 넣을 수 있으므로 dp = [1]*1001 로 선언한다. 

만약 나보다 작은 상자를 발견하면, 해당 상자를 나에게 넣는 것과 넣지 않는 것의 크기를 비교해서 더 큰 것을 넣는다. 

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

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

dp = [0] * 1000001

dp[1] = 1
dp[2] = 2 

for i in range(3,n+1):
  dp[i] = ( dp[i-2] + dp[i-1] ) % 15746

print(dp[n])

# 런타임 에러 해결 

dp = [0]*(n+1) 이런 식으로 작성하면 런타임 에러 남 

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

n = int(input())

dp = [0]*81

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

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

r = dp[n-1] + dp[n-1] + dp[n-2]

print( r+r )  

# 런타임 에러 

이유 :  dp = [0]*n 으로 했더니 런타임 에러가 났다.

         크기는 항상 주어진 값 보고 그 것 보다 하나 더 크게 잡아줄 것.

www.acmicpc.net/problem/13301

a = input()
b = input()

la, lb = len(a), len(b)

dp = [ [0]*(lb+1) for _ in range(la+1) ] 
lcs = [ ['']*(lb+1) for _ in range(la+1) ] 

for i in range(1,la+1):
  for j in range(1,lb+1):
    if a[i-1] == b[j-1] :
      dp[i][j] = 1+ dp[i-1][j-1]
      lcs[i][j] = lcs[i-1][j-1] + b[j-1] 
    else :
      if dp[i-1][j] > dp[i][j-1] : n,m = i-1, j 
      else : n, m = i, j-1 

      dp[i][j] = dp[n][m]
      lcs[i][j] = lcs[n][m]

print(dp[i][j])
print(lcs[i][j])

print(dp[i][j])
print(lcs[i][j])

a = input()
b = input() 

la = len(a)
lb = len(b)

dp = [ [0]*(lb+1) for _ in range(la+1) ]

for i in range(1,la+1):
  for j in range(1,lb+1):
    if a[i-1] == b[j-1] :
      dp[i][j] = 1+ dp[i-1][j-1] 
    else: 
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  
  # print(dp[i])

print( dp[la][lb] )

www.acmicpc.net/problem/9251

# DP 에서 자주 나오는 내용이므로 잘 이해해보자.  

DP 시간 복잡도   : O(mn)

완전 탐색 복잡도 : O(2^n)

입력 문자열 1 : n 

입력 문자열 2 : m 

step1 )  (n+1)*(m+1) 크기의 dp 배열을 만든다. 

step2 )  규칙 적용하기 

> 규칙 1 :  n[i] == m[i]  -> dp[i][j] = 1 + dp[i-1][j-1]  

               만약 양쪽 문자열 끝의 값이 같다면, 그 두 문자열을 제외한 앞 부분의 최대 길이에 1 을 더한다. 

> 규칙 2 :  n[i] != m[i]  -> dp[i][j] = max( dp[i-1][j] , dp[i][j-1] ) 

               만약 양쪽 문자열 끝의 값이 다르면, 각 문자열이 오기 전 단계의 최대 값을 유지한다. 

step3 ) 이해하기 

n = ABCDE

m = BXDE

   0  B  X  D  E  

0  0  0  0  0  0 

A  0  0  0  0  0     <- A와 BXDF 는 일치하는 값이 없다. 

B  0  1   1  1  1     <- AB와 B / BX / BXD / BXDE 를 비교한다고 생각하면 된다. 

C  0  1   1  1  1 

D  0  1   1  2  2  

E   0  1   1  2  3  

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

# 정답 ( 다이나믹 )