-
[Python] 백준(BOJ): 2293 동전1알고리즘/백준 2021. 12. 9. 19:14
문제
풀이
a. 접근법
N개의 동전을 사용하여 가치의 합이 K가 되는 경우의 수를 구해야 한다
knapsack 알고리즘을 이용하여 접근한다
ⓐ j가 coin[i]보다 작은 경우는, i번째 동전을 사용할 수 없으므로 DP[i][j] = DP[i-1][j]
ⓑ j가 coin[i]보다 크거나 같은 경우는, i번째 동전을 0개 ~ x(x*coin[i] <= j)개까지 사용할 수 있다.
따라서 점화식은 DP[i][j] = DP[i-1][j-coin[i]] + DP[i-1][j] (coin[i] <= j)b. 시간 초과 풀이
n, k = map(int, input().split()) coin = [] for i in range(n): coin.append(int(input())) coin.sort() dp = [0] * (k+1) for j in range(coin[0], k+1): dp[0][j] = 1 for i in range(1, n): for j in range(1, k+1): if j < coin[i]: dp[i][j] = dp[i-1][j] else: val = j while val > 0: dp[i][j] += dp[i-1][val] val -= coin[i] if val % coin[i] == 0: dp[i][j] += 1 print(dp[n-1][k])
계속해서 메모리, 시간 초과가 발생
런타임 에러의 경우, 동전의 가치에 대한 범위가 주어지지 않아서 발생함
(k의 범위는 1<k<10,000인데 동전의 가치는 100,000보다 작거나 같은 자연수 값을 가질 수 있음! 즉 k보다 큰 가치값을 가지는 동전 입력이 있을 수 있다는 말임)c. 풀이
i-1번째 DP에 i번째 DP를 덮어씌우는 방식으로 1차원 DP사용
n, k = map(int, input().split()) coin = [] for i in range(n): coin.append(int(input())) coin.sort() dp = [0] * (k+1) dp[0] = 1 for val in coin: for i in range(val, k + 1): dp[i] += dp[i - val] print(dp[k])
'알고리즘 > 백준' 카테고리의 다른 글
[Python] 백준(BOJ): 14890. 경사로 (0) 2023.01.30 [Python] 백준(BOJ): 1495 기타리스트 (1) 2021.12.29 [Python] 프로그래머스: 도둑질 (0) 2021.12.09 [Python] 백준(BOJ): 1931 회의실 배정 (0) 2021.10.24 [Python] 백준(BOJ): 1946 신입사원 (0) 2021.10.24