[백준/파이썬] 2091 : 동전

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

2091번: 동전

문제 요약 : 1,5,10,25 동전이 있다. 각 동전의 개수는 정해져 있고, 동전 개수 내로 X원을 만드는 가장 큰 경우의 수를 출력하라.

 

동전 시리즈 풀겠다고 했다가 동전한테 털림

18번의 시도 끝에 성공한거라 어떻게 성공한건지 기록해놓으려고 한다,,

어디가 틀렸는지 반례라도 알고 싶어서 검색을 많이 했는데, 파이썬으로 2091번을 푼 경우가 거의 없었고 질문도 답해주신 분들이 없었다.

그나마 검색에서 나오는 경우는 DFS였는데, 나는 DFS로 풀지 않았는데 답에 거의 가까워진 것 같아서 계속 고군분투한 것 같다 ㅠ 찾다보니 골드 5 -> 4 -> 3 이 된거였다.. ㅋㅋㅋㅋ 골드 5는 확실히 아니였던것 같다.

 

 

맞은 코드가 궁금하신 분은 제일 밑에 내려서 풀이 라고 해놓은 부분을 보면 될 듯 합니다.

 

시도 1 )

30% 실패

 

알고리즘 분류에 그리디가 있어 그리디를 사용해보았다.

 

큰 수 부터 작은 수 순으로 내려가며 값을 구했고, 구해진 최대값을 ans에 저장했다.

만약 이 때, 구해지지 않으면 0 0 0 0으로 빠져나온다.

 

다음 ans값에서 큰 수들을 작은 수로 대체할 수 있는지 확인한다.

위의 방법과 똑같이 큰수에서 작은 수 순으로 가며 그 값보다 작은 값으로 그 값을 만들 수 있는지 확인하며 ans값을 갱신해나가게 하였다..

coins = [0]*4   # 1센트 5센트 10센트 25센트
x,coins[0],coins[1],coins[2],coins[3] = map(int,input().split())
value = [1,5,10,25]
ans = [0]*4

for i in range(3,-1,-1) :   # 제일 적게 사용하는 경우
    tmp = min(x//value[i], coins[i])
    if tmp == 0 :
        continue
    ans[i] = tmp
    x = x-(tmp*value[i])
    coins[i] -= ans[i]
    
if x != 0 :
    print("0 0 0 0")
else :
    for i in range(3,0,-1):
        if ans[i] != 0 :
            while ans[i] != 0:
                x = value[i]
                ans2 = [0]*4
                coins2 = coins[:]
                for j in range(i-1,-1,-1):
                    tmp = min(x//value[j], coins2[j])
                    if tmp == 0:
                        continue
                    ans2[j] = tmp
                    x = x-(tmp*value[j])
                    coins2[j] -= ans2[j]
                if x == 0:
                    for k in range(i):
                        ans[k] += ans2[k]
                        coins[k] = coins2[k]
                    ans[i] -= 1
                else :
                    break
    print(*ans)

그리디 알고리즘이 성립하는 조건은 동전 중에 큰 수가 작은수의 배수일 때만 가능하다고 알고 있었는데,

검색해보니 1, 5, 10, 25 센트를 예시로 설명한 것이 많았다. 25는 10의 배수가 아니지않나..?

 

잘 읽어보면 그 경우에 우연찮게 된 것이었고, 정말 되는지 확인해보라는 것이 핵심이었다. 😅😅

 

https://hongjw1938.tistory.com/172

알고리즘 - 그리디 알고리즘(Greedy Algorithm)

성립하는 조건에 대해 친절하게 적어놓으신 것을 보고 다시 한번 개념을 정립했다.

 

 

시도 2 )

조금 파김치가 되었다,,🤪

coins = [0]*4   # 1센트 5센트 10센트 25센트
x,coins[0],coins[1],coins[2],coins[3] = map(int,input().split())
value = [1,5,10,25]
dp = [-1]*(x+1)
ans = [0]*4
dp[0] = 0

for i in range(4):
    print(i,"일 때,")
    for j in range(value[i],x+1):
        if j-value[i] <= coins[i]*value[i]:
            dp[j] = max(dp[j],dp[j-value[i]]+1)
        else:
            break
        
print(dp)

앞서 풀었던 동전문제와 유사한 것 같았다. 단지 여기선 동전개수 리미트가 생긴거?

그냥 총 개수만 구한다는 생각으로 풀리는지 시도해봤다.

 

70%에서 틀림

coins = [0]*4   # 1센트 5센트 10센트 25센트
x,coins[0],coins[1],coins[2],coins[3] = map(int,input().split())
value = [1,5,10,25]
dp = list([-1 for _ in range(5)]for _ in range(x+1))
for i in range(coins[0]+1):
    dp[i] = [i,0,0,0,i]

for i in range(1,4):  # 5센트부터
    for j in range(value[i],x+1):   # 센트 최소값부터 x값까지
        if (dp[j-value[i]][i]+1 <= coins[i]) :
            if dp[j-value[i]][0] == -1 :
                continue
            else:
                if dp[j][4] == -1:  # 아직 값이 안들어왔다는 것
                    for p in range(5):
                        dp[j][p] = dp[j-value[i]][p]
                    dp[j][i] += 1
                    dp[j][4] += 1
        else:
            break

if dp[-1][-1] == -1 :
    print("0 0 0 0")
else:
    print(*dp[-1][:4])

이때부터 거의 정답에 가까워졌는데, 세세한 문제점은 제외하고 큰 문제점을 위주로 보면

① if dp[j][4] == -1

② else: break

때문이었다.

 

 

1번을 저렇게 푼 이유는, 1센트부터 서서히 올라가기 때문에 dp값에 -1이 아닌 다른 값이 저장된 경우 무조건 그 경우가 가장 크다고 생각했기 때문이다.

그래서 사용한 동전개수가 값이 생기는 경우는 무조건 값이 없을 때에만 가능하다고 생각했다.

반례는 못 찾았지만, 혹시나 하는 마음에

dp[j-value[i]][4]+1 > dp[j][4] 로 변경하니 맞았음

 

 

2번은 사용가능한 동전 개수를 넘으면 그 다음 부터는 다 똑같겠지 않나 라는 생각으로 무조건 사용가능한 동전개수를 넘게되면 빠져나가고 다음 동전단위로 넘어갔다.

 

나와 같은 방식으로 푼 사람을 찾지 못하였는데, 유사하게 푼 사람들을 보니 이중 for문을 돌 때 센트부터 돌고 목표 값이 도는게 아닌 목표 값이 돌고 센트가 도는 것이 대부분이였다..

왜 그렇게 하는게 더 좋다고 생각했을까 ?

혹시 미리 break를 할 게 아니라 나중에는 동전 개수를 넘지 않는 경우가 나오는 게 아닌가 싶어서 else: break문을 제거해보았다.. 정답이였음

 

 

---

 

풀이 )

import sys
input = sys.stdin.readline

coins = [0]*4   # 1센트 5센트 10센트 25센트
x,coins[0],coins[1],coins[2],coins[3] = map(int,input().split())
value = [1,5,10,25]
dp = [[-1] * (5) for i in range(x + 1)]  # dp table

for d in range(min(x,coins[0])+1):    # 1센트
    dp[d] = [d,0,0,0,d]

for i in range(1,4):  # 5센트부터
    for j in range(value[i],x+1):   # 센트 최소값부터 x값까지
        if (dp[j-value[i]][i]+1 <= coins[i]) :  # 사용가능한 동전개수보다 작거나 같은지
            if dp[j-value[i]][4] == -1 :    # 현재 동전을 사용할 때, 나머지가 존재하는지
                continue    # 안하면 통과
            if dp[j-value[i]][4]+1 > dp[j][4]:  # 갱신하는 값이 더 큰지 확인
                    dp[j][:] = dp[j-value[i]][:]
                    dp[j][i] += 1
                    dp[j][4] += 1

if dp[-1][-1] == -1 :
    print(0,0,0,0)
else:
    print(*dp[-1][:4])

dp는 dp[현재목표값][사용한동전개수]로 이루어져있다.

사용한 동전 개수는 1센트, 5센트, 10센트, 25센트, 전체 순으로저장했다.

 

1센트의 경우 min(x,coins[0])을 안 해주면 1 2 0 0 2 같은 경우에서 오류가 난다.

 

이중 for문은 5센트부터 25센트까지 돌고, 현재 목표값은 현재 센트 값을 시작으로 x값까지 돈다.

j-value[i]는 언제나 0보다 커야하는데, 나는 센트를 먼저 돌았기 때문에 따로 확인해주지 않아도 되었다.

 

동전을 사용할 경우, 가지고 있는 동전개수 내에서 쓸 수 있는지 확인 해주고, 사용할 수 있다면

나머지가 존재하는지 확인해준다.

 

또한 그 나머지 값에서 +1을 해준 값이 현재 목표값의 전체 값보다 큰지 확인 후, 값을 갱신해준다.

 

 

성공! 맞은 사람을 보니 DFS가 더 빠르고 메모리도 적게 쓰는 듯 하여 나중엔 DFS로도 풀어볼까 한다💪