문제 : https://www.acmicpc.net/problem/1943
초기 구상과정
- dfs를 이용해서 완전 탐색해서 문제를 풀면 되지 않을까?
- dfs에 인자를 추가해서 조건 분기를 줘서 문제를 풀면 시간초과도 해결할 수 있을거야!
- 동전 종류와 갯수를 통해서 0 - N으로 나눠서 값들을 나눠어서 계속해서 문제를 만들어서 가져가면 되지 않을까?
초기 코드
import sys
sys.stdin = open('김병완_1943_동전분배_G3.txt', 'r')
# import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
# 시간초과, 도대체 어디서, 어떻게 DP를 적용해야하지?
def dfs(money, coin_idx):
tmp = 0
if money == quot:
return 1
if coin_idx == N:
return 0
if quot - money < min(coins):
return 0
else:
for cnt in range(coin_info[coins[coin_idx]] + 1):
if money + coins[coin_idx] * cnt > quot: continue
tmp = dfs(money + coins[coin_idx] * cnt, coin_idx + 1)
if tmp == 1: return 1
return 0
for tc in range(3):
# 동전 종류의 갯수
N = int(input())
coin_info = {}
total = 0
coins = [0] * N
for i in range(N):
coin, num = map(int, input().split())
coins[i] = coin
total += coin * num
coin_info[coin] = num
coins.sort(reverse=True)
quot = total >> 1
# print(coin_info)
result = dfs(0, 0)
print(result)동전 값의 크기가 큰 것부터 집어넣어서 최적해를 구해나가는 완전 탐색에 backtracking을 써서 시간초과를 해결해보려고 노력했다.
- 동전 종류를 모두 다 썼다.
if coin_idx == N:
return 0- 현재 값에서 목표값의 차이가 최소 동전의 값보다 더 작다.
if quot - money < min(coins):
return 0 더 이상 진행할 필요가 없으니 그냥 뒤돌아가자- 다음 동전을 더 넣으면 목표값보다 더 많다.
for cnt in range(coin_info[coins[coin_idx]] + 1):
if money + coins[coin_idx] * cnt > quot: continue
tmp = dfs(money + coins[coin_idx] * cnt, coin_idx + 1)
if tmp == 1: return 1 이건 들어가기 전에 차단하자결과는 시간초과, 틀렸습니다, 시간초과, 시간초과...
최종 코드
결국 dfs를 포기하고 다른 방법들을 찾았다. dfs로 풀고 싶어서 구선생님의 힘을 잠시 빌렸는데 이게 dfs가 아니란다. dp문제라고 한다. dp는 작은 단위로 쪼개서 위로 올라오면서 풀거나 점화식을 만들어서 푸는 것이라고 알고 있는데 dp란다. 이게 왜일까?
import sys
input = sys.stdin.readline
for tc in range(3):
# 동전 종류의 갯수
N = int(input())
coin_info = {}
total = 0
for i in range(N):
coin, num = map(int, input().split())
coin_info[coin] = num
total += coin * num
if total % 2:
print(0)
continue
quot = total >> 1
dp = [0] * (quot + 1) # 우리 관심은 딱 quot까지만이잖아
dp[0] = 1 # 0원부터 시작하니까 0원 체킹
for coin in coin_info:
if quot < coin: continue
for val in range(quot, -1, -1):
if dp[val]:
for cnt in range(coin_info[coin] + 1):
if val + coin * cnt > quot: continue
dp[val + coin * cnt] = 1
print(dp[quot])이게 우리가 원하는 값을 찾기 위해서 공백의 리스트를 만들어두는 데 이 인덱스가 우리가 원하는, 우리가 만들 수 있는 돈의 값을 체킹할 수 있는 리스트로 사용하는 것이다.
다만 우리가 원하는 값은 딱 절반으로 나눌 수 있는가?가 궁금하기 때문에 리스트는 더도 말고 덜도 말고 타겟보다 +1의 크기를 갖는 리스트를 만들어주면 된다.
뒤에서부터 리스트를 체킹을 하면서 우리가 가지고 있는 동전 중 값이 큰것부터 깔아가며 체킹이 되어있는 부분이 생기면 그 지점부터 동전 갯수를 배수로 가져가며 추가된 값들의 리스트를 체킹하여 표기하는 방식이다.
말로 표현하니 너무 정신이 없다. 그림으로 보자. ㅎ..
CASE 2
처음에는 0만 체킹이 되어있고 150부터 쭉 읽어보며 1을 찾는다. 결국 0원만 존재하고 있으니 0원에서 100원을 갯수만큼 더해서 그 인덱스에 1을 표기하는 방식이다. 하지만 100원이 2개여도 우리는 150원을 넘으면 관심이 없으니 100원만 찍고 끝.
두번째에서는 다시 뒤에서 읽어오며 100원이 찍혀있는 것을 확인. 100원에서부터 50원을 더해가며 그 인덱스를 찍는 방식으로 50을 더한 150의 값을 1로 변환.
이런 방식으로 모든 경우의 수를 체크하면 리스트에서는 만들 수 있는 값어치를 체킹을 모두 한 경우가 되어 우리는 원하는 값인 150에 1이 찍혀있는지 0이 찍혀있는지 확인하면 답을 체킹하는 것이다.
느낀점
굉장히 색달랐다. "이런 방식으로도 구현을 할 수 있구나"라고 생각했고 DP문제는 결국 아이디어 싸움이 되는 문제들이라는 것을 깨달았다. 결국 DP는 문제를 많이 풀어봐야겠다고 생각했다.
