[DP] - S2_1912_연속합

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

1912번: 연속합

 

 

📌- 풀이

DP문제를 항상 어렵게 생각했는데 DP문제 치고는 생각보다 간단하게 풀었던 것 같음.

 

1. 값이 이렇게 들어온다고 생각할 때, 각각 값이 들어올때마다 최대값을 저장해주자라는 생각을 함

 

10부터 시작해서 10은 10 하나이므로  최댓값이 10이고,

 

 

-4의 경우에는 10에다가 -4를 더하는 값이 최대기 때문에 -4를 더해서

 

이런 식의로 전의 값과 비교해서 최댓값을 저장하면서 진행을 한다.

 

진행을 하다가 보면 이전 값은 -40인데 현재 값은 70이다 이럴 경우에는 이전 값을 더 해버리면 현재 배열의 값이 30이 되어버려서 최댓값을 구할 수 없게 되므로 (이전 값 + 현재 값)이 0보다 크지만 현재 값보다 작은 경우에는 현재 값으로 초기화를 해준다.

 

if(arr[i-1] + n < n){
         arr[i] = n; // -> 여기에 해당하는 부분
}

 

마저 진행을 하면서 이전 배열의 값과 현재 자신의 값을 더한 값이 0보다 작을 때가 있는데 이럴때는 자기 자신을 넣어준다.

이렇게 하는 이유는 다음 값을 구할 때 이전 값이 필요하기 때문임

 

21에 -35를 더하지 않고 -35를 넣음

 

 

결과 적으로 새로운 배열을 사용하지 않고도 하나의 배열을 사용해서 결과 값이 나오게 되는데 

아래의 배열이 얻게 된 배열이고 해당 배열에서 제일 큰 값을 출력하게 되면 얻을 수 있는 가장 큰 수가 된다.

 

🔥 - Java 코드

 

package DP.S2_1912_연속합;

import java.io.*;
import java.util.*;

public class Main {
        public static int N;
        public static Integer[] arr;
    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());


        N = Integer.parseInt(st.nextToken());

        arr = new Integer[N];

        st = new StringTokenizer(br.readLine());
        arr[0] = Integer.parseInt(st.nextToken());
        for(int i=1;i<N;i++){
            int n = Integer.parseInt(st.nextToken());
            if(arr[i-1] + n <=0){
                arr[i] = n;
            }else{
                if(arr[i-1] + n < n){
                    arr[i] = n;
                }else{
                    arr[i] = arr[i-1] + n;
                }

            }

        }

        Arrays.sort(arr,Collections.reverseOrder());
        System.out.println(arr[0]);



    }

}