백준 4097번 수익 바로가기
시간 제한 : 1초
메모리 제한 : 256BM
레벨 : Silver 2
문제 설명
문제
연종이는 창업했다. 오늘은 창업한지 N일이 되었고, 매일매일 수익을 적어놓았다. 어느 날 연종이는 가장 많이 돈을 번 구간이 언제인지 궁금해졌다. 오늘이 창업한지 6일 되었고, 수익이 다음과 같다고 하자.
- 1일 : -3
- 2일 : 4
- 3일 : 9
- 4일 : -2
- 5일 : -5
- 6일 : 8
이때, 가장 많은 돈을 번 구간은 2~6까지이고 총 수입은 14이다.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 N이 주어져 있다. (1 <= N <= 250,000)
둘째 줄부터 N개의 줄에는 매일 매일의 수일 P가 주어진다. (-10,000 <= P <= 10,000)
수익은 첫 날부터 순서대로 주어진다. 입력의 마지막 줄에는 0이 주어진다.
출력
각 테스트 케이스에 대해서 가장 많은 수익을 올린 구간의 수익을 출력한다. 단, 구간이 비어있으면 안 된다.
예제
예제 입력 1
6
-3
4
9
-2
-5
8
2
-1000
-19
0
예제 출력 1
14
-19
문제 풀이 - DP
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
StringBuilder build = new StringBuilder();
while(true) {
int N = Integer.parseInt(read.readLine());
if(N == 0) break;
int[] profits = new int[N + 1];
for(int i = 1; i <= N; i++) {
profits[i] = Integer.parseInt(read.readLine());
}
int[] dp = new int[N + 1];
dp[1] = profits[1];
int max = -10001;
for(int i = 2; i <= N; i++) {
dp[i] = Math.max(profits[i], dp[i - 1] + profits[i]);
max = Math.max(max, dp[i]);
}
build.append(max).append("\n");
}
System.out.println(build);
}이 문제는 수익으로 음수가 들어왔을 때를 잘 고려해야 한다. 나의 경우, 처음에는 profits[i]가 음수일 때마다 구간을 분리해야 하나 생각했다. 하지만 예를 들어, 구간이 5 -4 7 8로 구성되어 있다면, -4를 포함하여 최대 수입을 계산해야 한다는 것을 깨달았다. 아래는 비슷하게 고려해야 할 경우들이다.
구간 1 : -3 5 1
구간 2 : -19 -1
구간 3 : 6 -2 5 11
구간 1의 경우 -3 + 5의 결과는 양수지만, dp[i]는 dp[i - 1] + profits[i]가 아닌 profits[i]가 되어야 한다.
구간 2의 경우 -19 + -1의 결과는 음수지만, 마찬가지로 dp[i] = profits[i]가 되어야 한다.
구간 3의 경우 구간에 음수가 있지만, 구간을 나누는 게 아니라 음수를 포함해서 계산해야 최대값이 나온다.
따라서 아래와 같은 점화식을 도출해냈다.
dp[i] = Math.max(profits[i], dp[i - 1] + profits[i]
처음에는 dp[i - 1] + profits[i]가 음수일 때와 양수일 때를 따로 구분해서 식을 작성하였다. 하지만 결국 모든 경우를 계산했을 때, 점화식이 같게 나오는 것을 보고 조건을 따로 두지 않고 하나의 식으로 작성하게 되었다. 중간에 음수가 있는 경우에도 profits[i] < dp[i - 1] + profits[i]기 때문에 의도한 방향으로 계산이 진행된다.
이런 유형의 문제를 풀 때마다 풀이법을 까먹어서 확실히 정리를 해야겠다는 생각이 들어 블로그를 작성하게 되었다.
