목록Algorithms/DP (Dynamic Programming) (16)
# 첫 접근 # +, -, * , // # 이전 경우의 수에 대해서만 다음 과정을 반복함... # 오답 def solution(N, number): answer = 1 dp = [[5]] while answer number: continue else: temp.append(v//N) temp.append(int(str(v)+str(N))) answer += 1 if number in temp: return answer dp.append(temp) return -1 def solution(N, number): dp = [0, {N}] if N == number: return 1 for i in range(2, 9): case_set = {int(str(N)*i)} for j in range(1, i//2+..
# m 열 n 행 # (1,1) (m,n) def solution(m, n, puddles): dp = [[0]*(m+1) for _ in range(n+1)] # 웅덩이 체크 -> -1 for x, y in puddles: dp[y][x] = -1 # 세로줄 채우기 for y in range(1, n+1): # 이전 값이 웅덩이이면 종료 if dp[y-1][1] == -1: break else: dp[y][1] = 1 # 가로줄 채우기 for x in range(1, m+1): if dp[1][x-1] == -1: break else: dp[1][x] = 1 for i in range(2, n+1): for j in range(2, m+1): if dp[i][j] == -1: continue # 둘다 ..
https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net from copy import deepcopy n = int(input()) a = list(map(int, input().split())) # dp[i] : i 까지 왔을 때, 합의 최대 dp = deepcopy(a) rev = [i for i in range(n)] idx = 0 # 현재위치 # for i in range(1, n):..
https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 � www.acmicpc.net # 누적합 - 합들의 누적을 미리 구해놓는 것 a = [i for i in range(10)] print(a) for i in range(1, 10): a[i] = a[i-1] + a[i] print(a) # dp[i] = i 까지의 합 # i 부터 j 까지의 합은 dp[i] - dp[i-1] ------- 풀이: # 2 차원 배열의 누적합 n, m = map(in..
n = int(input()) lines = [] for _ in range(n): lines.append(list(map(int, input().split()))) lines = sorted(lines, key=lambda x: x[0]) # LIS result = [[] for _ in range(n)] for i in range(n): if i == 0: result[i].append(lines[i][1]) else: for j in range(0, i): if result[j][-1] < lines[i][1]: if len(result[i]) - 1 < len(result[j]): result[i] = result[j] + [lines[i][1]] if not result[i]: result[i]..