백준 31265 훈련

문제

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

31265번: 훈련

 

각훈련마다 훈련을 하나씩 넣는걸로 이해해서 해맸다. 

 

풀이

간단하게 훈련상황을 하나라고 가정하자.

1~M에서 훈련시간으로 가능한 것만 체크해주면 될 것같다. 

훈련시간의 조합으로 브루트포싱을 하기엔 d=1000이므로 무리가 있다.

만약에 t1이 훈련시간으로 가능했고, 현재 훈련의 시간이 x라면 t1+x도 훈련시간으로 가능하다.

따라서 한 훈련상황에서 훈련시간으로 가능한 시간들은 해당 코드로 효율적으로 구할 수 있다.

bag = [[False] * (M + 1) for _ in range(N)]
# 훈련상황을 하나로 제한했으므로 idx I (0 <= I < N)에 대해서만 판단해본다.
for t in 훈련상황[I]:
	for i in range(1, M + 1):
    	if i-t >= 0 and bag[I][i-t]:
        	bag[I][i] = True

만약에 훈련상황마다 훈련이 하나라면? 그냥 배낭문제 코드 복붙하면 된다.

bag = [[False] * (M + 1) for _ in range(N)]
time = [....] # 길이가 N인 list time에는 각 훈련상황마다 하나의 훈련시간이 있다.
for i in range(N):
	t = time[i]
    for j in range(M + 1):
    	if t - j >= 0 and bag[i-1][t - j]:
        	bag[i][j] = True

 

문제 지문 자체가 전형적인 배낭문제를 시사하고 있긴 하다.

 

문제는 훈련상황이 여러개고, 각 상황마다 적어도 하나의 훈련을 해야한다.

현재 시간 x에 대해

A.훈련상황이 하나일땐 같은 훈련상황에서  x - t(i,j)가 true인지 판단했다.

B.훈련상황이 여러개이고 각 훈련상황마다 하나의 훈련일땐 이전 훈련상황에서 x - t(i,j)가 true인지 판단했다. 

두 조건중 하나이상 만족한다면 x는 올바른 훈련시간이다.

for i in range(N):
    for t in 훈련상황[i]:
        tmp = []
        for j in range(M + 1):
            if j - t >= 0 and (bag[i][j-t] or bag[i-1][j-t]) and not bag[i][j]:
                tmp.append(j)
        for j in tmp:
            bag[i][j] = True

코드작성법은 두 조건만 만족하면 되므로 여러개지일 것이다.

조건 A는 bag[i][j-t] 조건B는 bag[i-1][j-t]가 true인지 판단하면 된다.

같은 훈련으로 인해 bag이 true로 갱신되는걸 막고 해당 훈련상황에서 가능한 훈련시간을 담기위해 tmp란 list를 만들었다.

중복을 지우기위해 시간 j에 대해 bag[i][j]가 false에서 true로 바뀔때에만 tmp에 j를 넣어줬다.