DP

https://www.acmicpc.net/problem/5569 코드w, h = map(int, input().split())dp = [[[0]*4 for _ in range(h)] for _ in range(w)]# 값 초기화for i in range(1, w): dp[i][0][1] = 1for j in range(1, h): dp[0][j][3] = 1for i in range(1, w): for j in range(1, h): dp[i][j][0] = dp[i-1][j][3] # 계속 오른쪽으로 가다가 이번에 위로 온 경우 dp[i][j][1] = (dp[i-1][j][0]+dp[i-1][j][1]) % 100000 # 계속 위로 dp..

https://www.acmicpc.net/problem/15990 코드dp = [[0]*3 for _ in range(100001)] # 1열은 이번에 1 더했을 때, 2열은 2, 3열은 3 더했을 때dp[1][0] = 1dp[2][1] = 1dp[3] = [1, 1, 1]for i in range(4, 100001): dp[i][0] = (dp[i-1][1]+dp[i-1][2]) % 1_000_000_009 dp[i][1] = (dp[i-2][0]+dp[i-2][2]) % 1_000_000_009 dp[i][2] = (dp[i-3][0]+dp[i-3][1]) % 1_000_000_009for _ in range(int(input())): n = int(input()) pr..

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]에는 계속 이..

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] != [..