본문 바로가기
728x90
SMALL

Algorithm/DP7

[백준] 9084번 : 동전 (파이썬) DP 문제 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 💡 풀이 코드 import sys t = int(sys.stdin.readline()) for _ in range(t): n = int(sys.stdin.readline()) c = list(map(int, sys.stdin.readline().split())) price = int(sys.stdin.readline()) dp = [[0] * (price + 1) for.. 2024. 2. 18.
[백준] 2294번 : 동전 2 (파이썬) 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 sys n, 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] = 0 def coin2(n, coin, .. 2024. 2. 18.
[백준] 11054번 : 가장 긴 바이토닉 부분 수열 (파이썬) DP 문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net ▪︎ 내 코드 import sys n = 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[i] = max(dp[i], .. 2024. 1. 22.
[백준] 2565번 : 전깃줄 (파이썬) 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, .. 2024. 1. 20.
[백준] 9465번 : 스티커 (파이썬) 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을 차근차근 채워나갈 것이기 때문에 ➡️⬇️⬆️⬅️ 방향 중 ⬆️⬅️ 방향의 스티커만 고려해서 피해 붙어주면 된다. 처음에 내가 좀 헤맸던게 문제.. 2024. 1. 6.
[백준] 11053번 : 가장 긴 증가하는 부분 수열 (파이썬) 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].. 2024. 1. 5.
320x100
LIST

티스토리툴바