https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제풀이 위 문제는 거스름돈 5원과 2원으로 주어진 돈을 거슬러 줘야 하는데 이때 동전을 최소한으로 사용하여 거슬러 줘야 한다. 먼저, 15원까지 동전의 수를 나열해 보았다. 나열해 본 결과 반복되는 패턴이 있음을 알 수 있다. 주어진 돈이 5의 배수가 아니면 주어진 돈 n 원에 대한 동전의 개수는 n - 2원에 대한 동전의 개수 + 1인 것을 알 수 있었다. 때문에 위 문제는 다이내믹 프로그래밍을 활용하여 문제를 해결할 수 있다. var n = Int(readLine()!)! var result = 0 var dp..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net Code let NK = readLine()!.split(separator: " ").map { Int($0)! } let N = NK[0] var K = NK[1] var coins: [Int] = [] var result = 0 for _ in 0.. K { break } coins.append(coin) } for i in 0..

https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 풀이과정 위 문제의 경우 강산이의 L일 휴가 동안 몇일 캠핑장을 이용할 수 있는지 계산하는 문제이다. 해당 캠핑장의 경우 연속된 P일 중 L일을 사용할 수 있다고 한다. 1번 케이스를 예로 들면, 강산의 휴가 기간은 20일이며, 캠핑장의 경우 연속된 8일 동안 5일을 사용할 수 있다. 강산이의 휴가를 8로 나눠보면, 몫이 2이고, 나머지가 4이다. 즉, 강산이의 휴가를 8일씩 나눠보면 8일이..