[Baekjoon] 2293. 동전1

문제 링크

https://www.acmicpc.net/problem/2293

문제 해석

• n 가지 종류의 동전
• 동전을 사용해서 k 원이 되는 경우의 개수를 리턴

문제 해결

1. 처음부터 다 조합해서 경우 구하기

• coin 0번째 부터 , coin 끝까지 순회
• 합계가 k 보다 작을때까지 반복

슈도 코드

recur(index,sum)
	if index == n:
		return count +1
	if sum >k:
		return count
	i = 0
	while True:
		sum + coin[index]*i > k:
			break
		recur (index+1,sum+coin[index]*1)
print(recur(0,0))

제출 코드

n , k = map(int,input().split())
coins = []
for i in range(n):
    coins.append(int(input()))
coins.sort(reverse=True)
test_ary = []
def dfs(index,sum,k):
    if sum ==k:
        test_ary.append(0)
        return
    if sum>k or index==n:
        return
    i = 0 
    while True:
        temp = i*coins[index] + sum
        if temp >k:
            break
        i +=1
        dfs(index+1,temp,k)
dfs(0,0,k)
print(len(test_ary))

=> 시간 초과

2. dfs 로 앞에서부터 경우의 수 증가

• 시간 초과 문제가 나서 , 문제 분류에 보니 DP가 있었다.
• 만들어 질 수 있는 경우를 모두 더해 나가서 마지막 k 를 return

슈도 코드

possible = [0] *(k+1)
possible[0]=1

for coin in coins
	for index in range(coin,k+1)
		case = possible[index-coin]
		possible[index] += case
print(possible[k])

사담

• DP 문제는 , 바로 생각 하지 않으면 절대 풀 수 없는 문제인 거 같다.
• 분류 를 보지 않고 , 바로 생각할 수 있는 실력을 기르자

Writed By Obisidan