너무나도 이해하기 힘든 문제였다.
이때까지의 피보나치 같은 DP 느낌에 머리가 익숙해져서 뭔가 조금만 다르게 생각하는 것도 잘 안되었다.
🤨 정답까지의 과정
문제 풀기 전 항상 주석으로 생각을 먼저 정리해본다.
//연속된 숫자들의 합
//일단 +만 더할 것인가..근데 -1 되있고 10000되 있는건?
//-를 포함해서 연속된 숫자까지 되니까 마이너스도 포함해야한다..
//1~2 1~3 1~4 1~5 1~6
//2~3 2~4 2~5..
//다음으로 넘어갈때마다 이 전에 있는 값을 어떻게 ..음
//[1] = 10 / 10 -4 / 10 -4 3
//[2] = -4 / -4 3
//[3] = 31. +만 더할까?
사실 가장 큰 숫자를 얻는 방법으로 제일 쉽게 떠오른 게 +만 더하는 것이였다. 그런데 당연하게도 이 문제가 그렇게 만만치 않았다.
일정 문제에서는 그렇게 되지만 예를 들어
2 1 -4 3 4 -4 6 5 -5 1
가장 큰 수는 14이고,
2 1 -4 [ 3 4 -4 6 5 -5 1 ]
이렇게 [] 연속된 숫자가 최댓값이다!
마이너스를 포함하더라도 더 큰 숫자가 나올 수 있는 것이다.
2. DP를 쓴다하더라도 2~4, 2~5, 3~6..?
이 부분에서 정말 오래 막혔다.
DP를 쓰는 것은 이미 계산한 것들을 줄이는? 것이 핵심으로 알고 있었고 그것을 응용하려고 하니
2~4 2~5 2~6..이런 것들을 계산한 테이블을 만들어야하나..싶은 생각만 들고 더 발전된 생각이 들지 않았다.
DP를 쓴다하더라도 처음부터 계산을 해나갈것이고 그럼 중간 시작~ 중간 끝인 연속된 값은 어떻게 최댓값을 찾느냐 하는 게 방법이 도저히 안 떠올랐다.
코드를 검색해서 찾아봤는데도 이해가 바로 안되서 유튜브로 강의하는 영상을 찾아봤다..
그 후 이해할 수 있었다!!
https://www.youtube.com/watch?v=fbBa5PuTtl0&ab_channel=%EB%A7%88%EB%8F%84%EB%A6%AC%EC%BD%94%EB%94%A9
😎 깨달음
이 문제에서 DP는 항상 가장 큰 것을 고르지 않는다.
애초에 DP는 가장 큰 것을 고른다 라는 생각이 머리에 너무 박혀있었다..
그러니까 다른 사람들의 풀이에서
10 -4 가 있을 때 Dp[2] = 6 이라는 부분에서
Dp[2]는 10이랑 -4가 있을 때 굳이 -4를 안 더하는 10이 되어야 하는 거 아니야? 라는 생각이 있었고, 생각보다 그 생각이 굳어져있었다.
그런데 이 문제에서 집중해야할 것은 연속된 수라는거다..지금 당장은 이게 최대가 아닐 수 있어도 언젠가 포텐이 터질 수 있다는 거다.
그러니까 DP에는 연속된 숫자들의 합이 들어간다.
합을 진행해나가면서 현재 기본 ary에 들어가있는 수 vs DP에 쌓아지고 있는 수를 비교했을 때 막 아무렇게나 더하다가는 너무 큰 마이너스를 더하는 불상사가 발생할 것이다 그런 경우에는 연속되던 것을 끊는다!
정답 코드
import java.io.*;
import java.util.Scanner;
public class Main {
public static int[] table;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] ary = new int[n];
table = new int[n];
for (int i = 0; i < n; i++) {
ary[i] = sc.nextInt();
}
table[0] = ary[0];
int max = table[0];
for (int i = 1; i < n; i++) {
table[i] = Math.max(ary[i], table[i - 1] + ary[i]);
if (max < table[i]) max = table[i];
}
System.out.print(max);
}
}