DP

문제 링크 https://www.acmicpc.net/problem/1463 문제 해설 Idea Dynamic Programming N에 대해 조건을 만족하는 경우에서 3으로 나누기, 2로 나누기, 1을 빼는 연산을 반복 수행하고 각각의 연산횟수 별로 도출할 수 있는 값을 모두 저장 앞선 결과를 모두 활용해 다음 결과에 대한 모든 경우를 탐색하고 결과 집합에 1이 있을 시 탐색을 종료 1이 포함된 마지막 집합의 인덱스 번호를 최소 연산횟수로 출력 Data Size N: 1 <= int <= 10^6 해설 코드 1 2 3 4 5 6 7 8 9 10 11 N = int(input()) dp = [{N,}] while 1 not in dp[-1]: dp....

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42895 문제 해설 Idea Dynamic Programming S[1] = {N} S[2] = {NN, N+N, N-N, N*N, N/N} S[3] = {NNN, S[2] (+,-,*,/) S[1][y], …} 2부터 8까지의 범위를 가진 i와 1부터 i-1까지의 범위를 가진 j에 대해, S[j]와 S[i-j]의 사칙연산 결과를 S[i]에 추가하고 해당 집합이 number를 포함하는지 검증 Time Complexity DP: O(1) Data Size N: 1 <= int <= 9 number: 1 <= int <= 32,000 answer: int <= 8 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 from itertools import product def solution(N, number): S = [set() for _ in range(9)] if N == number: return 1 else: S[1]....

문제 링크 https://www.acmicpc.net/problem/2302 문제 해설 Idea Dynamic Programming 자리를 옮길 수 있는 연속되는 좌석의 수는 피보나치 수열을 따름 (S[i] = F[i+1]) VIP 좌석 번호를 기준으로 연속되는 좌석의 수를 리스트로 저장 모든 연속되는 좌석 수에 대한 피보나치 수를 곱하고 출력 Sequence S2 (1,2) -> (1,2), (2,1) = 2(F3) S3 (1,2,3) -> (1,2,3), (2,1,3), (1,3,2) = 3(F4) S4 (1,2,3,4) -> (1,2,3,4), (2,1,3,4), (1,2,4,3), (1,3,2,4), (2,1,4,3) = 5(F5) S5 (1,2,3,4,5) -> (1,2,3,4,5), (1,2,4,3,5), (1,2,3,5,4), (2,1,3,4,5), (2,1,4,3,5), (2,1,3,5,4), (1,3,2,4,5), (1,3,2,5,4) = 8(F6)...

문제 링크 https://www.acmicpc.net/problem/1495 문제 해설 Idea Dynamic Programming P[i] = max(P[i-1]+V[i-1],P[i-1]-V[i-1]), 0 <= P[i] <= M 모든 P[i-1]가 P[i+1]에 영향을 줄 수 있기 때문에 범위 내 모든 값을 집합에 저장 마지막 곡에 대한 P가 존재할 경우 최댓값을 출력하고, 없을 경우 -1을 출력 Time Complexity DP: O(NM) = 50,000 Data Size N: 1 <= int <= 50 M: 1 <= int <= 1,000 S: 0 <= int <= M V: int * N 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 N, S, M = map(int, input()....