[백준] Silver II. 연속합

https://www.acmicpc.net/problem/1912

 

사용 알고리즘

• 다이나믹 프로그래밍

 

풀이

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

/*
    테이블: d[i]: i번째 숫자를 보고있을 때의 연속된 숫자들의 최댓값
    점화식: d[i] = max(d[i], d[i-1] + s[i])
 */
public class Main {
    static int n;
    static int [] s, d;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        s = new int[n];
        d = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            s[i] = Integer.parseInt(st.nextToken());
        }

        d[0] = s[0];
        int max = d[0];
        for(int i = 1; i < n; i++) {
            d[i] = Math.max(s[i], d[i - 1] + s[i]);
            max = Math.max(max, d[i]);
        }
        System.out.println(max);
    }
}

 

 

회고

 

문제를 풀면서 점화식과 테이블을 얼추 답과 비슷하게 설정했는데, 틀린 부분이 있었다.

점화식: d[i] = max(d[i], d[i-1] + s[i])

 

내가 세운 점화식인데, 정답은 이렇다.

점화식: d[i] = max(s[i], d[i-1] + s[i])

 

 

d[i-1]은 이전까지의 모든 연속된 숫자들의 총합이고, 현재 숫자인 s[i]를 더했을 때와 기존 s[i]의 값을 비교해서 더 큰 쪽을 d[i]로 재설정 해줘야 했다.

 

내가 세운 점화식은, d[i]를 초기화 해주지 않아서, 만약에 값이 0보다 작은 경우에도 불구하고 0으로 초기화를 해주었다.

10
10 -4 3 1 5 6 -35 12 21 -1

 

-35일때, 현재까지 연속된 숫자의 합인 -14가 저장되어야 하는데 0이 저장되기 때문에 문제가 됐다.

 

5
-1 -2 -3 -4 -5

 

이 예제에서 더 직관적으로 와닿는데,

d[1] = max(d[1], d[0] + s[1]) => d[1]이 0으로 초기화 되어있기 때문에 0이된다.

 

d[1] = max(s[1], d[0] + s[1]) => max(-1,-2)이기 때문에 -1이 성공적으로 저장이 된다.