DP 문제https://www.acmicpc.net/problem/9095💡 풀이코드 (성공 1)import sys t = int(sys.stdin.readline())def dynamic(n): dp = [0 for _ in range(n + 1)] dp[0] = 1 dp[1] = 1 dp[2] = 2 dp[3] = 4 for i in range(4, n + 1): dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] print(dp[n])for _ in range(t): n = int(sys.stdin.readline()) if n == 0: print(1) elif n == 1: p..

DP, 누적합 문제https://www.acmicpc.net/problem/2616 이 문제는 냅색 알고리즘의 변형으로도 볼 수 있을 것 같다.누적합을 저장해준 (1차원) 배열을 만들고, 해당 배열을 활용하여 소형 기관차 3대로 최대 운송할 수 있는 손님수를 구하는 문제이다. 초기 접근 방식객차의 수, 소형 기관차가 최대로 끌 수 있는 객차의 수, 소형 기관차의 갯수(3)에 대한 정보가 주어졌다.처음에 이 문제를 보고 DP로 풀어야겠다고 생각했다. 그러나 초기에는 r = 소형 기관차가 최대로 끌 수 있는 객차의 수, c = 객차의 수에 대한 DP 배열의 형태를 구상하였기에 문제가 생각보다 쉽게 풀리지 않았다.3대의 소형 기관차가 최대로 끌 수 있는 객차의 수는 서로 같다. 여기서 "최대"라는 말에 포커스..

DP 문제https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)www.acmicpc.net ▪︎  내 코드import sysn = int(sys.stdin.readline())arr = list(map(int, sys.stdin.readline().split()))def bitonic(n, arr): dp = [1] * n dp2 = [1] * n for i in range(1, n): for j in range(i): if arr[i] > arr[j]..

DP 문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net (1) 처음에 생각한 방식 한 스티커 기준으로 바로 인접한 ➡️⬇️⬆️⬅️ 방향에 있는 스티커는 붙힐 수 없다. 이 문제를 보자마자 dp로 풀어야겠다고 생각했다. dp는 bottom-up(작은 -> 큰) approach으로 table을 차근차근 채워나갈 것이기 때문에 ➡️⬇️⬆️⬅️ 방향 중 ⬆️⬅️ 방향의 스티커만 고려해서 피해 붙어주면 된다. 처음에 내가 좀 헤맸던게 문제..

DP 문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net (1) 처음에 실패한 이유 # 가장 긴 증가하는 부분 수열 (실버2) import sys n = int(sys.stdin.readline()) l = list(map(int, sys.stdin.readline().split())) dp = [0] * n maxNum = 0 finalCnt = 1 # dp[0]..

DP 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net (1) 처음에 내가 생각한 방식 (실패) # 계단오르기 (실버3) import sys n = int(sys.stdin.readline()) score = [] for _ in range(n): i = int(sys.stdin.readline()) score.append(i) def ans(score): dp = [0] * n dp[n -1] = score[n - 1] dp[n - 2] = score..