2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 고등학교 확률과 통계 시간에 경우의 수 파트에서 다루는 내용이다. 주어진 동전의 종류에 따라, 합을 만들 수 있는 경우의 수를 구하는 문제이다. 처음에는 경우의 수 문제를 풀듯이 가장 가치가 큰 동전부터 하나씩 줄여가며 갯수를 세주는 방식으로 구현하였는데, 동전 종류의 개수가 고정이 아니므로 재귀를 활용하였다. import sys sys.setrecursionlimit(10**9) n, k = map(int, input().split()) coins = list(..

16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 주어진 A값의 뒤에 1을 붙이거나 A를 2배하여 B로 도달하게 만드는 연산 횟수의 최솟값을 구하는 문제다. 요새 동적 계획법 연습을 많이 하기도 했고, 최근 푼 문제인 25418 - 정수 a를 k로 만들기가 동적 계획법으로 해결할 수 있는데, 이 문제와 결이 비슷하다고 생각하여 접근하였다가 메모리 초과가 나왔다. 그도 그럴 것이 B의 최댓값이 10^9 이므로 배열에 담기엔 너무 큰 수이긴 했다. (+ 동적 계획법은 배열에 일부 최적해를 계산해서 담는 방식인데, 작성한 코드를 보니 최적해를 계산한다기보단 그저 값을 할당하는 과정일 뿐이였다.) 1. DP let input = readLine..