[Baekjoon] 14767_Flow Shop

문제(출처: https://www.acmicpc.net/problem/14767)

---

< Flow Shop >

 

문제 풀이 

 

각 단계를 진행할 때 이전 수확기의 단계가 다 진행되었는지 확인한다. 

 

my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class _14767_ { // Flow Shop

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int arr[][] = new int[n][m];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < m; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int dp[][] = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (i == 0) {
					if (j == 0) {
						dp[i][j] = arr[i][j];
						continue;
					}
					dp[i][j] = dp[i][j - 1] + arr[i][j];
				} else {
					if (j == 0) {
						dp[i][j] = dp[i - 1][j] + arr[i][j];
					} else {
						if (dp[i][j - 1] < dp[i - 1][j]) {
							dp[i][j] = dp[i - 1][j] + arr[i][j];
						} else {
							dp[i][j] = dp[i][j - 1] + arr[i][j];
						}
					}
				}
			}
		}
		for (int i = 0; i < n; i++) {
			bw.write(dp[i][m - 1] + " ");
		}
		bw.flush();
	}
}

변수)
n, m : 수확기 수, 단계 수 
arr : 각 수확기의 각 단계 수행 시간
dp : 각 단계까지 완료되는 시간

 

수확기 수, 단계 수를 입력받는다. 각 수확기의 각 단계 수행 시간을 입력받아 arr에 저장한다. arr을 살펴보며, 첫 번째 수확기는 차례대로 진행하고, 다음 수확기부터 이전 수확기의 시간을 확인한다. 첫 번째 단계에서는 (이전 수확기 첫 단계 완료 시간) + (현재 수확기 첫 단계 완료 시간)으로 구하고, 나머지는 이전 단계에서 끝난 시간이 이전 수확기의 현재 단계 시간보다 빠르다면 이전 수확기 시간을 기준으로 현재 단계를 수행한다. 이전 단계에서 끝난 시간이 이전 수확기의 현재 단계 시간보다 느리다면 이전 단계를 기준으로 현재 단계를 수행한다. 

 

최종 dp배열의 마지막열을 출력한다.     

---

---