14697번: 방 배정하기
정보 초등학교 6학년 여학생들은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러
www.acmicpc.net
두 가지 방법이 있다.
1. 삼중 포문을 이용하기
a,b,c,n = map(int, input().split())
count = 0
for i in range(n//a+1):
for j in range(n//b+1):
for k in range(n//c+1):
if a * i + b * j + c * k == n:
count = 1
if count == 1:
print(1)
else:
print(0)문제 그대로 해석하여 a,b,c의 경우의 수로 주어진 인원 n을 만들 수 있을 때 1을 출력하고 그렇지 않을 때 0을 출력한다.
단 i, j, k의 최댓값은 각각 n//a, n//b, n//c를 넣을 수 없으므로 range의 범위를 0부터 n//a까지 반환되도록 설정한다.
2. 다이나믹 프로그래밍(dp)을 이용하기 - bottop up 방식
a, b, c, n = list(map(int, input().split()))
dp = [0] * (300+1)
dp[a] = dp[b] = dp[c] = 1
for i in range(a, n+1):
for j in [a, b, c]:
if i >= j and dp[i - j]:
dp[i] = 1
print(dp[n])먼저 n의 최댓값은 300이므로 dp의 길이를 300으로 하고 0으로 초기화한다.
만약 인원이 x일 때 학생들을 배치할 수 있다면 dp[x] = 1, 그렇지 않다면 dp[x] = 0 으로 한다.
a,b,c에 대하여 학생들이 인원이 각각 a,b,c 일 경우 학생들을 배정할 수 있으므로(예: 학생 인원이 a명이라면 1,0,0)
dp[a] = dp[b] = dp[c] = 1로 초기화한다.
그리고 bottom-up 방식으로 dp 리스트를 가장 작은 숫자 a부터 300까지 값을 지정한다.
예를 들어 a,b,c가 5,9,12인 경우를 보자. 이 경우 n=5라면 앞서 언급한 것 처럼 배정 방법을 a,b,c = (1,0,0)으로 지정할 수 있다. 그리고 dp[6] = 0, dp[7] = 0, dp[8] = 0 , dp[9] = 1, dp[10] = 1, dp[11] = 0, dp[12] = 0, dp[13] = 0 이다.
이제부터 방 배치가 가능한 경우만 보자. dp[14]에선 (a,b,c) = (1,1,0)의 방식으로 학생들의 방을 배정할 수 있다. 그리고 다음 경우의 수는 dp[17]에선 (a,b,c) = (1,0,1) 방식으로 배치할 수 있다.
다음 두 예시를 통해 한 가지 결론을 내릴 수 있다. dp[5] = 1 이라면 5에 a,b,c 중 하나의 값을 대입했을 때 방 배치를 할 수 있다. n=5일 때 방 배치가 가능하다면 5+5인 경우, 5+9, 5+12일 때도 가능할 것이고, 17이 가능하다면 17+5, 17+9, 17+12의 방법도 가능할 것이다.
즉, dp[x] = 1이 성립한다면 dp[x+a], dp[x+b], dp[x+c]도 방 배치가 가능하다.
단, 방 배치는 인원 수가 양수일 때만 가능하므로 조건에 i>= j 을 통하여 리스트의 인덱스 값이 마이너스를 향하지 않도록 한다.
3. 다이나믹 프로그래밍을 이용하기 - top down 방식
A, B, C, N=map(int, input().split())
a=[-1 for _ in range(N+1)]
for i in range(min(A, N)):
a[i]=0
if A<=N:
a[A]=1
if B<=N:
a[B]=1
if C<=N:
a[C]=1
def f(n):
if a[n]==-1:
if n<B:
a[n]=f(n-A)
elif n<C:
a[n]=max(f(n-A), f(n-B))
else:
a[n]=max(f(n-A), f(n-B), f(n-C))
return a[n]
if N<A:
print(0)
else:
print(f(N))
#출처 : imsehwan, https://www.acmicpc.net/source/21713812임세환(imsehwan)님의 정답을 참고하였습니다.
먼저 원소 값을 세 가지 경우로 나누었다.
방 배치가 이루어지지 않았다면 -1, 학생 인원 배치가 불가능하다면 0, 학생 인원 배치가 가능하다면 1로 설정한다.
2번 방식과 마찬가지로 n명일 때 배치가 가능하다면 n-a명, n-b명, n-c명 일 때도 배치가 가능해야 한다.
함수 f(n)에 대하여 a[n]이 -1이라면(배치가 되어있지 않다면) n-a명, n-b명, n-c명일 때 배치가 가능한지 재귀적으로 확인한다. 재귀적으로 계속 확인하여 리스트의 값이 -1이 나오지 않을 때 재귀함수를 종료한다.
만약 f(n-a), f(n-b), f(n-c) 중 하나라도 1의 값을 반환한다면 1의 값을 반환하고,
-1이 반환되었다는 것은 최소 배치 인원인 a명보다 작을 때이므로 배치가 불가능 한 케이스이다. 따라서 0을 출력하도록 한다.