https://www.acmicpc.net/problem/4097 코드from sys import stdininput = stdin.readlinewhile True: n = int(input()) if n == 0: break p = [int(input()) for _ in range(n)] ans = 0 dp = [0]*n for i in range(n): dp[i] = max(dp[i-1]+p[i], p[i]) # 계속 이어나가기 vs 새로운 시작 print(max(dp)) dp[i]에는 i번째 원소까지 확인했을 때, 마지막 원소(i번째)가 포함된 부분 배열 중 가장 합이 큰 부분 배열의 합이 저장된다. 그러므로 dp[i]에는 계속 이..
dynamicprogramming
https://www.acmicpc.net/problem/3372 코드n = int(input())board = [list(map(int, input().split())) for _ in range(n)]dp = [[0]*n for _ in range(n)]dp[0][0] = 1for i in range(n): for j in range(n): if board[i][j] == 0: continue # 오른쪽 if j+board[i][j] dp[i][j]는 (i, j)까지 갈 수 있는 경로의 수를 저장한다. 출발점인 (0, 0)의 dp값을 1로 놓고, N × N 게임 보드의 각 칸을 살펴보며 현재 칸(i, j)에서 오른쪽과 아래로 board[..
https://www.acmicpc.net/problem/16432 코드import sysinput = sys.stdin.readlinen = int(input())arr = []for _ in range(n): input_data = list(map(int, input().split())) arr.append(input_data[1:])dp = [[[]for _ in range(10)] for _ in range(n)]for a in arr[0]: # 첫째날 dp[0][a] = [a]for i in range(1, n): for a in arr[i]: for j in range(1, 10): if a != j and dp[i-1][j] != [..
https://www.acmicpc.net/problem/2876 코드import sysinput = sys.stdin.readlinen = int(input())grades = [(0, 0)]for _ in range(n): a, b = map(int, input().split()) grades.append((a, b))dp = [[[0]*2 for _ in range(2)] for _ in range(n+1)] # 왼쪽 학생, 오른쪽 학생ans = [0, 5] # 명수, 그레이드for i in range(1, n+1): for j in range(2): # i번째 책상의 2명의 학생 dp[i][j][1] = grades[i][j] # 그레이드 ..
https://www.acmicpc.net/problem/14430 코드n, m = map(int, input().split())board = [list(map(int, input().split())) for _ in range(n)]dp = [[0]*(m+1) for _ in range(n+1)]for i in range(1, n+1): for j in range(1, m+1): dp[i][j] = max(dp[i-1][j], dp[i][j-1])+board[i-1][j-1] # 위 or 왼쪽에서print(dp[n][m]) 로봇은 아래나 오른쪽으로 한 칸만 이동할 수 있다. 그렇기 때문에 (i, j)칸까지 얻을 수 있는 자원의 최대 숫자는 한 칸 위와 한 칸 왼쪽 중 최대값과 현재..
