[Baekjoon] 4097_수익

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

---

< 수익 >

 

문제 풀이 

 

dp를 활용하여 가장 많은 수익을 올린 구간의 수익을 구한다. 

 

my solution (Java)

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

public class _4097_ { // 수익

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

		int n = 0;

		while ((n = Integer.parseInt(bf.readLine())) != 0) {

			int arr[] = new int[n];
			int dp[] = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(bf.readLine());
				dp[i] = arr[i];
			}

			int result = Integer.MIN_VALUE;

			for (int i = 1; i < n; i++) {
				dp[i] = Math.max(dp[i], dp[i - 1] + arr[i]);
				result = Math.max(result, dp[i]);
			}

			bw.write(result + "\n");
		}
		bw.flush();
	}
}

변수)
n : 일
arr : 매일매일의 수익
dp : 많은 수익을 올린 구간의 수익
result : 가장 많은 수익을 올린 구간의 수익 

 

0이 입력되기 전까지 n을 입력받는다. n만큼 매일매일의 수익을 입력받아 arr과 dp에 저장한다. 매일매일을 살펴보며 현재 값과, 전날의 값+현재 값 둘 중에 큰 값으로 업데이트한다. 최종 최댓값을 출력한다.

---

---