BOJ 백준 31265 훈련
문제 : https://www.acmicpc.net/problem/31265
[ 문제 요약 ]
- N 가지의 훈련 상황이 있고, 각 훈련 상황마다 특정 개수의 훈련이 들어가 있으며, 이 훈련의 각각의 시간이 주어진다. 각 훈련 상황마다 최소 1개 이상의 훈련을 선택해 M 시간을 초과하지 않는, 가장 큰 훈련 시간 총합을 출력합니다.
- 불가할 경우 - 1을 출력합니다.
- 훈련은 중복 선택 불가합니다.
[ 테스트 케이스 설명 ]
5 24 // 훈련상황 가지 수(1<=1,000), 훈련 최대시간(1<=10,000)
5 2 4 1 3 // 각 훈련 상황에 속한 훈련의 개수(1<=1,000)
23 7 11 3 2 // n줄에걸쳐 각 훈련 상황에 속한 훈련의 소요 시간을 나타내는 정수가 주어짐(1<=1,000)
8 10
5 17 20 9
13
1 24 3
// 답 : -1
[ 문제 해설 ]
훈련 상황마다 반드시 1개 이상 선택하지 않고, 단순히 훈련 중 최대 시간을 구하는 것이라면 일반 배낭문제로 쉽게 구할 수 있습니다.
하지만 문제는 훈련 상황마다 반드시 1개 이상 선택해야 합니다.
이런 훈련 상황마다 반드시 1개 이상 선택하는 것을 코드에 별도로 넣어 구현해야 할 거 같으나, 2차원 배열로 구현할 때, DP 전이 방식을 수정하면 그 조건은 자연스럽게 지켜지게 됩니다. 스스로 그 조건이 지켜지는 것입니다.
보통 2차원 배열로 DP를 구현할 때, 이전 순번에서 썼던 데이터를 현재로 가져오기 위해 이전 데이터를 현재로 복사합니다. 아래 코드와 같이 말입니다.
ex) dp[i][j] = dp[i - 1][j]
이 의미는 [ 그룹 i를 선택 없이 지나가도 된다 ]는 의미가 됩니다.
하지만 이 문제는 그룹당 반드시 하나 이상 골라야 하므로, 이 전이를 빼면 되는 것입니다.
이렇게 해서 [항상 그룹당 최소 하나는 선택]이라는 조건이 암묵적으로 보장되게 됩니다.
그렇다면 문제는 더 간단해진 것이고, 단순히 boolean 2차원 배열을 선언하여 배낭을 채워주기만 하면 됩니다.
아래는 정답 코드와, 그 코드를 좀 더 빠르게 개선한 코드 2개를 보여줍니다.
[ 정답 코드 ]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main{
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());// 훈련상황 가지 수(1<=1,000)
int M = Integer.parseInt(st.nextToken());// 훈련 최대시간(1<=10,000)
int cnt[] = new int[N + 1];
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++)
cnt[i] = Integer.parseInt(st.nextToken());
// dp[i][j] = i번째 그룹까지 고려했을 때, 합계가 j가 가능한가?
boolean[][] dp = new boolean[N + 1][M + 1];
dp[0][0] = true; // 아무것도 선택하지 않을 때 합 0은 가능
for(int i=1; i<=N; i++)
{
st = new StringTokenizer(br.readLine());
for(int c=0; c<cnt[i]; c++)
{
int t = Integer.parseInt(st.nextToken());
// 역순으로 순회하여 같은 시간을 중복 선택하지 않도록함
for(int m=M; m>=t; m--)
{
// dp[i-1][m-t] → 이전 그룹까지 합(m-t)이 가능했다면, 그룹 i에서 아이템 t를 선택해 m 달성
// dp[i][m-t] → 같은 그룹 i에서 이미 한 번 이상 선택해 합(m-t)이 가능했다면, 그룹 i에서 추가로 아이템 t 선택해 m 달성
// 이 둘만 허용하므로 그룹 i를 완전히 스킵하는 전이(dp[i][m] = dp[i-1][m])가 없어,
// 항상 그룹당 최소 1개는 선택이 보장된다.
if(dp[i-1][m-t] || dp[i][m-t])
dp[i][m] = true;
}
}
}
// dp[N]그룹에 최종적으로 true가 있는 것이 답이되므로 가장큰 M부터 탐색
for(int i=M; i>=0; i--)
{
if(dp[N][i])
{
System.out.print(i);
return;
}
}
System.out.print(-1);
}
}[ 속도 개선 코드 ]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main{
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());// 훈련상황 가지 수(1<=1,000)
int M = Integer.parseInt(st.nextToken());// 훈련 최대시간(1<=10,000)
int cnt[] = new int[N + 1];
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++)
cnt[i] = Integer.parseInt(st.nextToken());
// dp[j] = 합이 j인 상태가 마지막으로 업데이트된 그룹 번호
// 초기에는 아무 그룹도 사용되지 않았으니 -1
int dp[] = new int[M + 1];
Arrays.fill(dp, -1);
dp[0] = 0;// 합 0은 그룹 0(가짜 그룹)까지 가능
for(int i=1; i<=N; i++)
{
st = new StringTokenizer(br.readLine());
for(int c=0; c<cnt[i]; c++)
{
int t = Integer.parseInt(st.nextToken());
// 역순으로 순회하여 같은 시간을 중복 선택하지 않도록함
for(int m=M; m>=t; m--)
{
// 이전 그룹번호를 prev에 담아옴
int prev = dp[m - t];
// (1) prev == i-1: 그룹 i에서 첫 선택
// (2) prev == i : 그룹 i에서 이미 한 번 이상 선택한 상태
if(prev == i - 1 || prev == i)
dp[m] = i;
}
}
}
for(int i=M; i>=0; i--)
{
if(dp[i] == N)
{
System.out.print(i);
return;
}
}
System.out.print(-1);
}
}위 속도 개선 코드는, dp 배열을 1차원으로 선언하고, dp 안에 저장되는 값은 해당 시간의 합까지 구하기 위해 마지막으로 업데이트된 그룹번호를 두었습니다.
[ 속도 차이 ]
두번째 코드가 180ms로 18% 더 빠릅니다.