DP 문제https://www.acmicpc.net/problem/2294 2294번: 동전 2첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어www.acmicpc.net 💡 풀이 코드import sysn, k = map(int, sys.stdin.readline().split())coin = []for _ in range(n): value = int(sys.stdin.readline()) coin.append(value)dp = [10001] * (k + 1)dp[0] = 0def coin2(n, coin, k):..

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/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net ▪︎ 내 코드 (성공) import sys n = int(sys.stdin.readline()) elec = [] for i in range(n): start, end = map(int, sys.stdin.readline().split()) elec.append((start, end)) elec = sorted(elec, key=lambda x:x[1]) def electronic(elec, ..

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/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net (1) 처음 내 코드 (런타임 에러 - 실패) # 피보나치 수4 (실버5) import sys n = int(sys.stdin.readline()) dp = (n + 1) * [0] dp[0] = 0 dp[1] = 1 for i in range(2, n + 1): dp[i] = (dp[i - 1] + dp[i - 2]) print(dp[n]) 문..