bright

www.acmicpc.net/problem/10942

# 시간 초과

from collections import deque

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

result = [1]*m 

for i in range(m):
  s,e = map(int,input().split())
  if e-s <2 : continue 
  d = deque(data[s-1:e]) 
  while len(d) > 1 :
    if d.pop() != d.popleft() : 
      result[i] = 0 

for i in range(m): print(result[i])

# 정답 ( dp ) 

www.acmicpc.net/problem/10211

t = int(input())

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

  for i in range(1,len(data)):
    data[i] += data[i-1] if data[i-1]>0 else 0
  
  return max(data)

p = []

for i in range(t):
  p.append(max_sub())

for i in range(t):
  print(p[i])

www.acmicpc.net/problem/1890

import sys
n = int(input())

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

d = [ [0]*n for _ in range(n) ] 
d[0][0] = 1

for i in range(n):
  for j in range(n):
    if i == j == n-1 : break 
    a = graph[i][j]

    if i+ a < n :
      d[i+a][j] += d[i][j]
    if j+a < n : 
      d[i][j+a] += d[i][j]

print(d[n-1][n-1])

d[n-1][n-1] = 0 은 항상 만족하는 조건이다. 

만약  이중 for 문에서 n-1, n-1 인 경우를 빼지 않으면 a = 0이고 i+a<n 과 j+a<n 이 모두 True 가 되어 

더하지 않아도 되는 계산을 하게 된다. 

따라서 맨 마지막 경우를 빼는 조건을 반드시 넣어 주도록 한다. 

www.acmicpc.net/problem/9465

def sticker(n,data):

  data[0][1] += data[1][0] 
  data[1][1] += data[0][0] 

  for j in range(2,n):
    data[0][j] += max( data[1][j-2],  data[1][j-1] )
    data[1][j] += max ( data[0][j-2], data[0][j-1] )
  
  return max(data[0][n-1], data[1][n-1])

t = int(input())
t_print = []

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

  t_print.append ( sticker(n,data) )

for i in range(t):
  print( t_print[i] )

index 2 이상부터 2칸 전 대각선과 1칸 전 대각선 비교해서 더하기가 가능! 

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