코딩테스트/백준

[Dev-Ping9] 백준 13398번 : 연속합 2 (Java)

DevPing9_ 2021. 11. 8. 21:03

# Description

# 어떤 접근 방법이 좋을까?

 

1. 문제의 답은 최적의 해를 구하는 것

 

2. 이전의 해를 이용하여, 지금의 해를 구할 수 있는가?

(부분 구조가 성립하는가? => Yes) 

 

=> 1번과 2번 문항을 통해 DP를 적용 시킬 수 있다는 근거를 가지게 되었다.

 

3. 단순무식하게 풀었을 때 연산량이 많은가?

 

f(a) 를 a 부터 시작한 [연속합2] 의 최대라 정의 했을때,

=> 1~N , 2~N , 3~N, .... , N~N

=> O(N^2)

 

4. 공간의 제약이 많은가, 시간의 제약이 많은가

=> Description을 보면, 확실히 시간의 제약이 많다. (시간제한 및 n의 최대값)

=> 보통 1초에 1억번 연산가능 (N^2 이면, N=100_000일때, 1천억번 연산해야함 => 1천초 소요..)

# DP 배열 정의하기

  • 가장 중요한 부분이라 생각한다.
  • 수학식이 아닌 한글과 같은 인간의 언어로 정의가 가능해야 무얼할지 확신이 서기 때문이다.

 

접근 방법을 DP로 결정하게 된 이유는, 문제에서 정의 된 이전의 해(정답)로 지금의 해를 구할 수 있다는 것 이었다. 

그럼 최대한 해당 논리에서 벗어나지 않게 배열을 정의해야 한다.

 

문제의 해를 [연속합2]로 정의 하겠다.

 

문제에서 [연속합2]의 정의는 1개의 숫자를 제거하거나, 제거를 하지않았을 때의 부분수열의 최대 연속합이다.

 

즉, 우리가 사용할 DP 방식으로 풀어낼 때, Memoization 으로 사용할 배열의 정의는 아래와 같다.

 

연속합2(n) = n까지의 부분수열의 최대합 중 [ 1개의 숫자를 제거한 값 & 제거하지 않았을때의 값 ] 의 최댓값

 

# DP 배열 점화식(규칙) 찾기

 

위의 정의에 따라, 우리는 원하는 해를 구하기 위해, 두개의 저장된 값이 필요하다는 것을 알 수 있다.

 

[1] 1개의 숫자를 제거한 값

[2] 숫자를 제거하지 않았을때의 값 

 

* expeceted solution : [1] 과 [2] 중 최댓값

 

[1] 은 [2] 의 값을 토대로 만들어 진다. 그러므로, [2]를 먼저 정의한다.

 

[2] noDeleted[n] : n을 pick 했을때, n까지의 최대 연속수열의 합

  • 연속적인 수열이어야 하므로, 이전의 해인 n-1 등과의 관계를 맺기 위해선 n을 pick 했다고 정의를 내려야 dp1[n-1] 을 가져왔을때도 n-1 이 pick 되어있는 상태가 되기 때문이다.
  • noDeleted[n] = max(arr[n], noDeleted[n-1]+arr[n]) 

 

[1] oneDeleted[n] : n까지의 연속합 중, 1개의 숫자를 제거 했을때의 최대값 

  • oneDeleted[n] = max( n번째 숫자를 제거함, n번째 숫자를 제거하지 않음 )
  • oneDeleted[n] = max( noDeleted[n-1], oneDeleted[n-1]+arr[n] )

 

# 구현코드

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

public class Main{
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        /*
        noDeleted[n] : n pick 시 , n 까지의 최대 연속합
        oneDeleted[n] : 숫자 하나를 지웠을 때, n까지의 최대 연속합
               : [case1] drop arr[n] => noDeleted[n-1]
               : [case2] pick arr[n] => oneDeleted[n-1]+arr[n]
        */

        long noDeleted[] = new long[n];
        long oneDeleted[] = new long[n];

        noDeleted[0]=  arr[0]; oneDeleted[0]= arr[0];
        long result = arr[0];
        
        for(int i=1; i<n; i++){
            noDeleted[i] = Math.max(arr[i], noDeleted[i-1]+arr[i]);
            oneDeleted[i]= Math.max(noDeleted[i-1],oneDeleted[i-1]+arr[i]);
            result = Math.max(result, Math.max(noDeleted[i],oneDeleted[i]));
        }
        System.out.println(result);
    }
}

/*
15
100 -2000 -4 -1 3 1 5 6 -10 -2 -4 -1000 12 21 -1
*/

# 실행화면

 

 

728x90