[백준] 1912: 연속합

문제

문제 풀이

문제에서 주어진 조건에 따라 두가지 경우를 생각할 수 있다.

• i번째 해당하는 수만 더하는 경우
• i-1번째 해당하는 수에 연이어 i번째 해당하는 수를 더하는 경우

bottom-up방식을 이용하여
i번째 해당하는 수만 더하는 경우와 i-1번째 해당하는 수에 연이어 i번째 해당하는 수를 더하는 경우 중 어떤 것이 더 큰지를 나타낸다.

• dp[i] = Math.max(dp[i-1] + arr[i] , arr[i])
  여기서, dp[i-1]값을 통해서 i-2와 i-1을 연달아 계산할 것인지에 대해 결정되었으니 우리는 arr[i-1]만 연달아 계산해야하는지 판단하면 된다.

코드

import java.util.Scanner;

public class ANS1912 {

    static int N;
    static int[] dp, A;

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        //N입력
        N = sc.nextInt();

        //수열 A, 배열 dp 선언 및 초기화
        A = new int[N];
        dp = new int[N];
        for(int i = 0 ; i < N ;i++){
            A[i] = sc.nextInt();
            dp[i] = 0;
        }
        dp[0] = A[0];
        int max = A[0];

        for(int i = 1 ; i < N ; i++){
            dp[i] = Math.max(dp[i-1] + A[i], A[i]);
            max = Math.max(max,dp[i]);

        }

        System.out.println(max);


    }
}

진짜 오랜만에 내 힘으로 풀었다..
다들 쉬운 문제라고 하지만, 나도 쉽다고 느낀것은 그만큼 동적계획법에 대해 이해하고 성장했다는 거 아닐까라는 긍정적인 생각을 해본다!!