https://www.acmicpc.net/problem/20364코드from collections import dequeimport sysinput = sys.stdin.readlinen, q = map(int, input().split())dp = [-1]*(n+1) # dp[i]는 1번에서 i번까지 가는 길에 가장 처음 마주치는 점유된 땅 번호for i in range(q): want = int(input()) if dp[want] == -1: # 가는 길에 이미 점유된 땅이 없음 # 이 땅 아래로는 다 이 땅을 지나야만 한다고 표시 q = deque([want]) while q: now = q.popleft() ..
문제풀이/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[..
