Algorithm & Problem Solving/다이나믹 프로그래밍(Dynamic Programming)
-
[백준 5557] 1학년 (Python)Algorithm & Problem Solving/다이나믹 프로그래밍(Dynamic Programming) 2020. 12. 30. 18:22
www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제풀이 N, arr : 입력값 dp : 특정 인덱스에서 현재까지의 수가 나올 수 있는 경우의 수 => dp[idx번째][현재까지의 수] = 가능한 경우의 수 전형적인 다이나믹 프로그래밍 문제이다. N제한이 100인데, 처음에 이걸 안보고 그냥 재귀 프루트포스로 풀려했다가 바로 시간초과를 받았다.. ㅠㅠ 문제 꼼꼼히 보도록 해야한다..! 이 문제의 핵심은 가능한 수가 0이상 20이하 라는 것이다. 이를 ..
-
[백준 2091] 동전 (Python)Algorithm & Problem Solving/다이나믹 프로그래밍(Dynamic Programming) 2020. 11. 29. 22:17
www.acmicpc.net/problem/2091 2091번: 동전 첫째 줄에 다섯 정수 X(1 ≤ X ≤ 10,000), A, B, C, D(0 ≤ A, B, C, D ≤ 10,000)가 주어진다. www.acmicpc.net 문제풀이 X : 입력값(목표 금액) coin : 1, 5, 10, 25 센트 동전 갯수 (입력값) ans : X원 일때 최대 사용한 1, 5, 10, 25 센트 동전 갯수 check : check[i] = x i원을 만들기 위해 최대로 사용한 동전의 갯수 x개 used : 특정 money원을 만들기 위해 사용한 1, 5, 10, 25 센트 동전의 갯수 x : X원을 만들기 위해 필요한 최소 1센트 갯수 dfs(money, cnt) : 가능한 모든 경우를 확인해보기 위한 재귀 함..