🥕 [ 백준 2294 ] 동전 2 문제 링크 url : https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 🍒 문제 분석 n 가지 종류의 동전이 있다. 이 동전들을 적당히 사용해 가치의 합이 k원이 되도록 만들고 싶다. 그러면서 동전의 갯수를 최소로 하고 싶다. 이때 사용하는 최소의 동전 갯수를 구하여라. 🥑 코드 def sol(k): d = [10001]*10001 for coin in coin_list: for i..
dp
🥕 [ 백준 2293 ] 동전 1 문제 링크 url : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 🍒 문제 분석 동전의 종류 n과 이를 이용해 만들어야하는 k원이 주어진다. 그리고 각 동전의 단위가 몇인지 알려준다. 이를 통해 k원을 만드는 경우의 수를 구해야한다. 가령 n = 3, k = 5 , 동전의 종류가 [1, 2, 5] 라면 1원 짜리 5개 1원 짜리 3개, 2원 짜리 1개 1원 짜리 1개, 2원 짜리 2개 5원 짜리 1개 하여 4..
[1로 만들기] 정수 X를 입력해, 5 로 나누거나, 3으로 나누거나, 2 로 나누거나, 1을 빼는 연산을 반복하여 1을 갖겠끔 하는 최단 연산의 갯수를 구하시오 도식화를 해보고 느낀 점은 1부터 해서 바텀 업 연산을 해야겠다. 1부터 X값 까지 최단 연산의 갯수를 다 구하면 되지 않을까? 근데 어떻게 연산 갯수 세는걸 어떻게 구현해야할지 모르겠어서 책을 봤다. ( 졸면서 5시간 고민 했는데 점화식이라는 개념이 미쳐 떠오르지 않았다. ) 점화식을 구해서 : \( a_i = min(a_{i-1},a_{i/2},a_{a/3},a_{a/5})+1 \) 점화식을 토대로 소스 코드를 작성한다. def sol(X): # df 테이블 초기화, d[1] = 0 d = [0]*(X+1) for i in range(1,X..
