[Baekjoon] 5953_Profits

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

---

< Profits >

 

문제 풀이 

 

연속된 기간 중 합이 가장 큰 값을 구하기 위해 dp를 사용하여 문제를 해결한다. 

 

my solution (Java)

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

public class _5953_ { // Profits

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

		int n = Integer.parseInt(bf.readLine());

		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];
		}

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

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

		System.out.println(result);

	}

}

변수)
n : 날짜 수
arr : 날의 순이익
dp : 연속된 날짜 구간 중 이익의 합 최대
result : 연속된 기간 동안 얻을 수 있는 최대 이익의 합 

 

날짜 수를 입력받는다. 날짜 수만큼 날의 순이익을 입력받아 arr에 저장하고 dp를 초기화한다. dp값을 살펴보며 현재값과 dp[i-1]+arr[i] 값 중 최댓값으로 업데이트한다. 최종 dp를 살펴보며 최댓값을 구해 출력한다. 

---

---