14697번 - 방 배정하기(python3)

문제 링크 : https://www.acmicpc.net/problem/14697

 

 

브루트포스 알고리즘을 이용해서, 주어진 인원을 남는 사람 없이 3종류의 방에 배정 가능한가를 따지는 문제입니다. Input이 5 9 12 113이면, 5명/9명/12명이 들어갈 수 있는 방이 여러 개 있고 113명을 각 방에 모두 넣을 수 있는지 체크하면 됩니다. 5인실 4개, 9인실 5개, 12인실 4개를 사용하면 113명을 남김없이 배정할 수 있습니다. 2종류의 방만 사용해서 5인실 10개, 9인실 7개를 사용해도 되구요.

 

그래서 처음 접근했던 방법은 5x + 9y + 12z = 113인 식을 만들고, x=0일 때-y=0일 때-z, x=0일 때-y=1일 때-z... 이런 식으로 돌아보려고 했습니다. 그런데 아래 링크의 블로그에서 획기적인 방법을 찾아냈습니다.

 

블로그 링크 : https://docp.tistory.com/entry/boj-14697

짱해커가 되어보자

위에 언급한 예시를 이용하면, n=0부터 n=113까지 훑으면서 현재 n이 기존의 가능한 숫자와 5, 9, 12 차이가 나는지를 확인합니다. 문제에서 주어지는 최대 인원수가 300이니까 301개의 0을 가지는 리스트를 만들고, n=5, 9, 12인 경우는 가능하니까 1로 둡니다. 이제 n=1인 경우부터 훑는데, 예를 들어 n=10이면 list[10-5], list[10-9], list[10-12]를 확인해서 세 경우 중 1이 있으면 10도 가능하다고 할 수 있겠죠. 이런 식으로 list[n]까지 훑었을 때 0인지 1인지에 따라 남는 인원 없이 방 배정이 가능한가를 확인할 수 있습니다. 

 

사실 이게 동적 계획법일텐데, 학부 알고리즘 수업시간에 배웠음에도 가물가물 하네요... 문제를 보고 풀 수 있는 아이디어가 빠르게 생각났으면 좋겠습니다. 물론 많은 문제를 풀어봐야겠죠.

 

a, b, c, n = map(int, input().split())

lst = [0]*301 #문제에서 주어진 최대 인원수 300

#가능한 case를 1로 처리
lst[a] = 1
lst[b] = 1
lst[c] = 1

for i in range(1, n+1):
    if lst[i] or lst[i-a] or lst[i-b] or lst[i-c]:
        lst[i] = 1
    else:
        lst[i] = 0
print(lst[n])