clohi 님의 블로그

https://www.acmicpc.net/problem/1965 문제 코드import sysinput = sys.stdin.readlinen = int(input())box = list(map(int, input().split()))dp = [1] * nfor i in range(n): for j in range(i): if(box[i] > box[j]): dp[i] = max(dp[i], dp[j] + 1)print(max(dp)) 문제 풀이 - DP 문제를 봤을 때 DP를 이용해서 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 문제를 푸는 것과 똑같다. 상자 크기 배열에서 앞에 있는 상자가 뒤에 있는 상자보다 작을 때만..

https://www.acmicpc.net/problem/1149 문제 코드 import sysinput = sys.stdin.readlinen = int(input())rgb= []for _ in range(n): rgb.append(list(map(int, input().split())))dp = [[0] * 3 for _ in range(n)]dp[0] = rgb[0]for i in range(1, n): dp[i][0] = rgb[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = rgb[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = rgb[i][2] + min(dp[i-1][0], dp[i-1][1])pr..

https://www.acmicpc.net/problem/11048 문제 코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())dp = [[0 for _ in range(m+1)] for _ in range(n+1)]maze = []for i in range(n): maze.append(list(map(int, input().split())))for j in range(1, n+1): for k in range(1, m+1): dp[j][k] = max(dp[j-1][k-1], dp[j-1][k], dp[j][k-1]) + maze[j-1][k-1]print(dp[n][m]) 문제 풀이 - dp dp로 어렵지..

https://www.acmicpc.net/problem/11726  문제코드 import sysinput = sys.stdin.readlinedp = [0] * 1001n = int(input())dp[1] = 1dp[2] = 2for i in range(3, 1001): dp[i] = (dp[i-1] + dp[i-2]) % 10007print(dp[n])  풀이 - DP전형적인 DP 문제이다. 규칙만 찾는다면 쉽게 풀 수 있는 문제 ! 일단 경우의 수를 생각해보면 n = 1 일때랑 n = 2일때는 쉽게 구할 수 있다.  이어서 n = 3 , n = 4인 경우도 구해보면  이런 식으로 직사각형을 만들 수 있다.  여기서 규칙을 찾아보면 n = 3 인 경우는 n = 1 인 경우에서 노란색 부분 (2..