백준 1943 동전 분배 - 파이썬

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

1943번: 동전 분배

 

 

dp로 해결할 수 있는 냅색 문제이다. 

Python3을 이용해 AC를 받은 사람이 단 4명으로, 그냥 Pypy로 제출하는 것이 정신 건강에 이롭다.

난 그마저도 시간 초과, 오답 파티를 했다.

 

 

 

일단 input을 받으면서 선생님한테 받은 전체 금액을 계산한다.

만약 전체 금액이 홀수라면 윤화와 준희가 모두 만족할 수는 없으므로 굳이 계산을 할 필요 없이 0을 출력하고 넘어간다.

 

반띵이 가능한 경우에는 실제로 분배가 가능한지 확인해주어야 한다.

일단 dp라는 boolean 배열을 만들었다.

dp[n]은 '주어진 동전들로 n원만큼 지불할 수 있다'는 의미이다.

0원은 언제고 지불할 수 있으니 True로 초기화하고, 1원 ~ (목표금액)까지는 아직 모르겠으니 False로 초기화한다.

여기서 목표금액은 전체 금액의 반띵 값이다.

 

coins 리스트에 넣어둔 각각의 동전을 살펴보면서 dp 배열을 업데이트해준다.

예를 들어서 이번에 확인할 값이 [100, 1] 이란 건 100원짜리 동전이 하나 있다는 소리이다.

그럼 dp 배열에서 동전 값(100)부터 목표금액까지의 모든 index의 elements를 다 살펴봐줘야 한다.

dp[index - 100]이 True라면, (index-100) 원을 주어진 동전들로 낼 수 있다는 의미인데, 나한테 100원 동전이 하나 더 생겼으니 당연히 index원도 지불할 수 있다.

따라서 dp[index]를 True로 업데이트해주면 된다.

 

다만 주의할 점이 있는데, 배열을 앞에서부터 탐색하면 안 된다.

탐색과 동시에 dp 배열이 갱신되기 때문에 같은 동전에 의해 갱신된 값을 뒤쪽 원소가 이미 지불 가능했던 값으로 착각할 수 있다.

그렇기 때문에 목표금액부터 지금 살펴보는 동전의 금액까지 거꾸로 dp를 업데이트해줘야 한다.

 

만약 같은 동전이 여러 개인 경우라면?

이번에 살펴볼 동전이 [100, 3]라고 해도 동전이 하나일 때와 크게 다르지는 않다.

dp[index-100]이 True라면 dp[index]도 True로 갱신해주면 된다.

다만, dp[index+100], dp[index+200]도 True일 테니 for문을 이용해 처리해주면 된다.

이때, dp의 범위가 전체 금액이 아닌 반띵 금액까지이므로 index range도 확인해줘야 한다.

 

dp[목표금액], 즉 dp[-1]이 True가 되는 건 반띵이 가능하다는 의미이다.

answer을 1로 갱신하고 break 해서 빠져나오면 되겠다.

만약 끝까지 dp[-1]이 False라면 answer은 계속 0일 것이다.

출력해주고 다음 테스트케이스를 살펴보면 된다.

 

 

 

난 89~92%에서 계~속 시간 초과가 떴었다.

시간 조금이라도 더 아껴본다고 coins 배열을 내림차순으로 정렬하고, 반띵 금액보다 동전 값이 크면 break 하는 방식으로 코드를 계속 만져줬는데도 시간 초과가 떴었다.

그 이유는 동전이 여러 개인 경우에 한 번에 확인할 수 있는 걸 하나씩 확인해줘서였다.

[100, 3]을 확인해야 할 때 [100, 1], [100, 1], [100, 1]로 확인했었다.

확인해야 할 범위가 커지면 당연히 느릴 수밖에.

 

 

for _ in range(3):
    total = 0 # 선생님한테 받은 전체 금액
    coins = [] 
   
    # input 받으면서 전체 액수 구하기
    for _ in range(int(input())):
        C, N = map(int, input().split())
        total += C * N
        coins.append([C, N])

    # 홀수는 반으로 안나눠짐 > 굳이 확인 안해봐도 됨
    if total % 2 == 1:
        print(0)
        continue

    total //= 2
    # dp[n]의 의미 == 주어진 동전들로 n원을 만들 수 있는가?
    dp = [True] + [False] * total

    answer = 0
    for i in range(len(coins)):
        C, N = coins[i]
        
        # 거꾸로 탐색하면서 지불 가능한 액수 갱신
        for n in range(total, C-1, -1):
            if dp[n-C]:
                for j in range(N):
                    if n + C * j <= total:
                        dp[n + C * j] = True
                    else:
                        break
                        
        if dp[-1]: # 반띵 가능!
            answer = 1
            break

    print(answer)