문제
공장에 제품을 생산하는 두 조립라인이 있다.
조립 라인은 아래 그림처럼, 처음에 부품을 준비하는 준비단계를 거쳐(s0,s1), 자신의 조립라인 단계를 통과하거나(a0,0~a0,n, a1,0~a1,n), 혹은 다른 조립라인으로 이동해서(t0,1 등) 단계를 마친 후, 마지막에 최종점검 단계를 거쳐서(e0,e1) 조립이 완료된다.
각 단계별 소요시간 a와, 다른 라인으로 이동할 때 걸리는 시간 t 등이 각각 다르게 주어졌을 때, 최소 시간안에 조립이 완료될 수 있는 경로를 제시하고 그 때 소요되는 총 소요시간을 구하시오.
예를 들어, 아래 그림처럼 문제가 주어졌을 때, 최소 이동단계는 E0 -> A0,0 -> A1,1 -> C1 이고, 최소소요시간은 10이다.
(2+3+1+2+2=10)
이동단계를 단계당 라인번호로 표현하면, Step0:0 -> Step1:1
입력파일
문제로 주어지는 입력파일내 데이터 형식은 다음과 같다.
테스트_개수
n
e0 c0
a0,0 a0,1 ... a0,n-2 a0,n-1
e1 a1,0 a1,1 ... a1,n-2 a1,n-1 c1
t0,0 t0,1 ... t0,n-2
t1,0 t1,1 ... t1,n-2
입력파일 예는 다음과 같다.
2
2
2 4
3 3
1
3 2
5 2
3
6
2 3
7 9 3 4 8 4
2 3 1 3 4
4 2
8 5 6 4 5 7
2 1 2 2 1
출력 형식(예)
Test #1
최소소요시간: 10
실행 순서:E0 -> 0 -> 1 -> C1
문제 소스
다음 코드를 활용해서 작성하시오.
package dynamic;
import java.io.File;
import java.util.Scanner;
public class AssemblyLine {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(new File("res/AssemblyLine.in"));
int T, N;
T = sc.nextInt();
for (int testNum = 1; testNum <= T; testNum++) {
N = sc.nextInt(); // 단계 수
int[] e = new int[2];// e[0]:0번 라인
int[] c = new int[2];
int[][] a = new int[2][N];
int[][] t = new int[2][N - 1];
// 1. 0번라인: e0, c0
e[0] = sc.nextInt();
c[0] = sc.nextInt();
// 2. 0번라인: a[0][0]~a[0][n-1]
for (int i = 0; i < N; i++) {
a[0][i] = sc.nextInt();
}
// 3. 0번라인: t[0][0]~t[0][n-2]
for (int i = 0; i < N - 1; i++) {
t[0][i] = sc.nextInt();
}
// 4. 1번라인: e1, c1
e[1] = sc.nextInt();
c[1] = sc.nextInt();
// 5. 1번라인: a[1][0]~a[1][n-1]
for (int i = 0; i < N; i++) {
a[1][i] = sc.nextInt();
}
// 6. 1번라인: t[1][0]~t[1][n-2]
for (int i = 0; i < N - 1; i++) {
t[1][i] = sc.nextInt();
}
// path={0,0,1,1,0,...}
int[] path = new int[N];
int min_time = assembly(N, e, a, t, c, path);
print(testNum,min_time,path);
System.out.println("");
}
}
static void print(int testNum, int min_time, int[] path){
System.out.println("Test #" + testNum);
System.out.println("min process time:" + min_time);
if(path[0]==0){
System.out.print("E0 -> ");
}else{
System.out.print("E1 -> ");
}
for (int i = 0; i < path.length; i++) {
System.out.print(path[i] + " -> ");
}
if(path[path.length-1]==0){
System.out.print("C0");
}else{
System.out.print("C1");
}
System.out.println("");
}
private static int assembly(int n, int[] e, int[][] a, int[][] t, int[] c, int[] path) {
return 0;
}
}
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
풀이
전형적인 다이니믹 알고리즘 형태의 문제이다. 최종단을 기준으로 했을 때, 문제 조건을 만족하는 앞 단을 재귀적으로 찾는.
먼저 점화식을 도출해보자.
어떤 단계까지의 소요시간을 f라하면 다음과 같은 식이 성립된다.
단계: 0~(n-1)
0라인의 소요시간: f[0][0], f[0][1] ... f[0][n-1]
1라인의 소요시간: f[1][0], f[1][1] ... f[1][n-1]
f[0][0] = e[0] + a[0][0]
f[1][0] = e[1] + a[1][0]
if (j>0)
f[0][j] = min(f[0][j-1]+a[0][j] , f[1][j-1]+t[1][j-1]+a[0][j])
f[1][j] = min(f[1][j-1]+a[1][j] , f[0][j-1]+t[0][j-1]+a[1][j])
f[0][0]이라고 하면, 0번 라인의 0단계까지 걸리는 시간을 의미하고,
이것은 초기 부품준비시간인 e[0]에, 0단계에서 소요되는 시간인 a[0][0]을 더한 값이 된다.
즉, f[0][0] = e[0] + a[0][0]
1번라인에 대해서도, f[1][0] = e[1] + a[1][0]
1단계 이상에서의 값은, 같은 라인으로부터 온 경로만 생각할 것이 아니라, 다른 라인에서 온 경로도 고려해야 한다. 다른 경로에서 오는 경우는 라인 전환비용인 t가 추가되므로, 1단계 이상의 값인 j단계에서의 최소시간은 아래와 같이 표현될 수 있다.
f[0][j] = min (0번 라인의 j-1번째 값 + j번 단계 소요시간 , 1번라인의 j-1번째 값 + 1번라인에서 0번라인으로의 전환비용 + j번 단계 소요시간)
=min(f[0][j-1]+a[0][j] , f[1][j-1]+t[1][j-1]+a[0][j])
f[1][j] = min(f[1][j-1]+a[1][j] , f[0][j-1]+t[0][j-1]+a[1][j])
* 2차원 배열이어서, 꺽쇄가 많아 보기에 헷갈릴 수 있지만, 같은 라인에서 오는가, 아니면 다른 라인쪽에서 오는가를 형상화하며 생각하면, 그리 어렵지 않게 이해할 수 있을 것이다.
이렇게 정의하면, 주어진 문제는 0번라인의 최종단계에서의 값인 (f[0][n-1] + c[0])와 , 1번라인 최종값인 (f[1][n-1] + c[1])중에서, 작은 값을 찾아내는 것이 된다.
f_min = min(f[0][n-1] + c[0] , f[1][n-1] + c[1])
이제 하나씩 구현을 해보자.
먼저, 문제코드를 보면, 최소소요시간을 리턴하고, path[]에 최소경로를 넣어야하는 assembly() 메서드를 구현하도록 되어 있다.
int[] path = new int[N];
int min_time = assembly(N, e, a, t, c, path);
이 assembly()를, 위에서 얘기했던 함수 f를 호출해서, f_min을 구해내는 형태로 작성하자.
private static int assembly(int n, int[] e, int[][] a, int[][] t, int[] c, int[] path) {
int[] path0 = new int[n];
int[] path1 = new int[n];
int minF0 = F(0, n - 1, e, a, t, c, path0) + c[0];
int minF1 = F(1, n - 1, e, a, t, c, path1) + c[1];
if (minF0 < minF1) {
path0[n-1]=0;
System.arraycopy(path0, 0, path, 0, path.length);
return minF0;
} else {
path1[n-1]=1;
System.arraycopy(path1, 0, path, 0, path.length);
return minF1;
}
}
F라는 함수를 호출해서 0번 라인의 끝단(n-1번째)에서의 최솟값과(minF0), 1번 라인에 대한 최솟값(minF1)을 구해서 비교하는 것을 볼 수 있겠다.
이제 핵심은 F함수를 구현하는 것이다.
다음과 같이 구현될 수 있다.
private static int F(int line, int j, int[] e, int[][] a, int[][] t, int[] c, int[] path) {
if (j == 0) {
return e[line] + a[line][0];
}
int other = (line + 1) % 2;
int A = F(line, j - 1, e, a, t, c, path) + a[line][j];
int B = F(other, j - 1, e, a, t, c, path) + t[other][j - 1] + a[line][j];
if (A < B) {
path[j - 1] = line;
return A;
} else {
path[j - 1] = other;
return B;
}
}
처음 부분에서 도출했던 점화식을 그대로 사용했음을 알 수 있다.
Base: j==0 이면, 초기 0번째 단계를 의미하므로, 초기준비단계값인 e와 0단계 소요시간을 더한 값이 된다.
f[0] = e[0] + a[0][0]
f[1] = e[1] + a[1][0]
점화식
A: 같은 라인의 '전 단계'에서 왔을 때 값
B: 다른 라인에서, 전환비용(t)을 감수하면서 왔을 때 값
이 둘을 비교해서 작은 쪽을 선택
이처럼 재귀호출을 사용해서 일단 테스트를 해본다. (assembly와 F 메서드를 구현해서 돌려본다.)
그러면 아래 처럼 해답이 잘 출력될 것임.
Test #1
min process time:10
E0 -> 0 -> 1 -> C1
Test #2
min process time:38
E0 -> 0 -> 1 -> 0 -> 1 -> 1 -> 0 -> C0
그러나, 이처럼 입력수가 작을 때는 재귀호출이 별 문제 안되나, 단계수가 많은 문제에 대해서는 재귀호출을 하면 지정시간에 수행할 수 없을 수 있다. 아래처럼 메모이제이션 기법을 써서 F메서드를 개선하자.
private static int F_memo(int line, int j, int[] e, int[][] a, int[][] t, int[] c,
int[] path, int[][] table) {
if (j == 0) {
table[line][j] = e[line] + a[line][0];
return table[line][j];
}
int other = (line + 1) % 2;
if(table[line][j-1]==0){
table[line][j-1] = F_memo(line, j - 1, e, a, t, c, path,table);
}
if(table[other][j-1]==0){
table[other][j-1] = F_memo(other, j - 1, e, a, t, c, path,table);
}
int A = table[line][j-1] + a[line][j];
int B = table[other][j-1] + t[other][j - 1] + a[line][j];
if (A < B) {
path[j - 1] = line;
return A;
} else {
path[j - 1] = other;
return B;
}
}
F()메서드를 호출하는 부분도 수정되야 한다.
int[][] table = new int[2][n];
int minF0 = F_memo(0, n - 1, e, a, t, c, path0,table) + c[0];
int minF1 = F_memo(1, n - 1, e, a, t, c, path1,table) + c[1];
전체 소스는 다음과 같다.
소스
package dynamic;
import java.io.File;
import java.util.Scanner;
public class AssemblyLine {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(new File("res/AssemblyLine.in"));
int T, N;
T = sc.nextInt();
for (int testNum = 1; testNum <= T; testNum++) {
N = sc.nextInt(); // 단계 수
int[] e = new int[2];// e[0]:0번 라인
int[] c = new int[2];
int[][] a = new int[2][N];
int[][] t = new int[2][N - 1];
// 1. 0번라인: e0, c0
e[0] = sc.nextInt();
c[0] = sc.nextInt();
// 2. 0번라인: a[0][0]~a[0][n-1]
for (int i = 0; i < N; i++) {
a[0][i] = sc.nextInt();
}
// 3. 0번라인: t[0][0]~t[0][n-2]
for (int i = 0; i < N - 1; i++) {
t[0][i] = sc.nextInt();
}
// 4. 1번라인: e1, c1
e[1] = sc.nextInt();
c[1] = sc.nextInt();
// 5. 1번라인: a[1][0]~a[1][n-1]
for (int i = 0; i < N; i++) {
a[1][i] = sc.nextInt();
}
// 6. 1번라인: t[1][0]~t[1][n-2]
for (int i = 0; i < N - 1; i++) {
t[1][i] = sc.nextInt();
}
// path={0,0,1,1,0,...}
int[] path = new int[N];
int min_time = assembly(N, e, a, t, c, path);
print(testNum,min_time,path);
System.out.println("");
}
}
static void print(int testNum, int min_time, int[] path){
System.out.println("Test #" + testNum);
System.out.println("min process time:" + min_time);
if(path[0]==0){
System.out.print("E0 -> ");
}else{
System.out.print("E1 -> ");
}
for (int i = 0; i < path.length; i++) {
System.out.print(path[i] + " -> ");
}
if(path[path.length-1]==0){
System.out.print("C0");
}else{
System.out.print("C1");
}
System.out.println("");
}
private static int assembly(int n, int[] e, int[][] a, int[][] t, int[] c, int[] path) {
int[] path0 = new int[n];
int[] path1 = new int[n];
//int minF0 = F(0, n - 1, e, a, t, c, path0) + c[0];
//int minF1 = F(1, n - 1, e, a, t, c, path1) + c[1];
int[][] table = new int[2][n];
int minF0 = F_memo(0, n - 1, e, a, t, c, path0,table) + c[0];
int minF1 = F_memo(1, n - 1, e, a, t, c, path1,table) + c[1];
if (minF0 < minF1) {
path0[n-1]=0;
System.arraycopy(path0, 0, path, 0, path.length);
return minF0;
} else {
path1[n-1]=1;
System.arraycopy(path1, 0, path, 0, path.length);
return minF1;
}
}
private static int F(int line, int j, int[] e, int[][] a, int[][] t, int[] c, int[] path) {
if (j == 0) {
return e[line] + a[line][0];
}
int other = (line + 1) % 2;
int A = F(line, j - 1, e, a, t, c, path) + a[line][j];
int B = F(other, j - 1, e, a, t, c, path) + t[other][j - 1] + a[line][j];
if (A < B) {
path[j - 1] = line;
return A;
} else {
path[j - 1] = other;
return B;
}
}
private static int F_memo(int line, int j, int[] e, int[][] a, int[][] t, int[] c, int[] path, int[][] table) {
if (j == 0) {
table[line][j] = e[line] + a[line][0];
return table[line][j];
}
int other = (line + 1) % 2;
if(table[line][j-1]==0){
table[line][j-1] = F_memo(line, j - 1, e, a, t, c, path,table);
}
if(table[other][j-1]==0){
table[other][j-1] = F_memo(other, j - 1, e, a, t, c, path,table);
}
int A = table[line][j-1] + a[line][j];
int B = table[other][j-1] + t[other][j - 1] + a[line][j];
if (A < B) {
path[j - 1] = line;
return A;
} else {
path[j - 1] = other;
return B;
}
}
}
-끝-
'알고리즘 > 알고리즘(Java)' 카테고리의 다른 글
| [분할정복]분할정복 개요-MergeSort (0) | 2015.10.26 |
|---|---|
| 25. [다이나믹]효율적인 행렬곱 순서 (0) | 2015.04.26 |
| 23. [다이나믹]옷 (0) | 2015.04.24 |
| 22. [다이나믹]배낭 문제 (Knapsack problem) (0) | 2015.04.21 |
| 21. [다이나믹] 최소 공정시간 찾기 (0) | 2015.04.21 |