[백준] 13398 연속합 2 - DP JAVA

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

13398번: 연속합 2

코드설명

DP 문제입니다.

 

이 문제에서 어려웠던점은 숫자 하나를 제거할 수 있다는 것입니다.

dp[N+1][2] 를 선언하여 [][0] : 아직 한번도 수를 제거하지않은경우, [][1] : 수를 한번 제거한경우 로 나누어서 해결합니다.

 

핵심로직입니다.,

dp[1][0] = arr[1];
dp[1][1] = arr[1];
answer = arr[1];
for(int i=2;i<=N;i++) {
    dp[i][0] = Math.max(arr[i], dp[i-1][0] + arr[i]); //특정수를 제거하지 않을 경우
    dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1] + arr[i]); // i번쨰 수를 제거하므로 dp[i-1][0]만 더해줍니다.
}
 
혹은
 
dp[1][0] = arr[1];
dp[1][1] = arr[1];
answer = arr[1];
for(int i=2;i<=N;i++) {
    dp[i][0] = Math.max(arr[i], dp[i-1][0] + arr[i]); //특정수를 제거하지 않을 경우
    dp[i][1] = Math.max(dp[i-2][0] + arr[i], dp[i-1][1] + arr[i]); //dp[i-2][0] + arr[i] 로 바꿔서 처리
}

가장 주의깊게 봐야할것은 dp[i][1] 입니다. dp[i-1][0] 에서 arr[i]를 더하는 것을 제거한다는점을 생각합니다.

 

가장 의문이 생기는점은 초기화값으로 dp[1][1] = arr[1] 로 왜 설정하는지 의문이 생깁니다.

왜냐하면, 첫번쨰 dp값에서 특정수로 첫번쨰 값을 제거한 경우가 존재할텐데 dp[1][1]  에서 첫번쨰 수를 제거했다면 0 이어야하는것 아닌가라고 생각이 들기 떄문입니다.

아직 정확한 이유를 알지 못하겠으나, 추측한바는 이렇게 초기화 함으로써 이후에 연산에서 원활히 사용할 수 있습니다.

이때 만약 dp[i][1] = 0 으로 설정할경우에는 음수인 경우를 고려하지 못하므로 dp[1][1] = arr[1] 로 설정해야만 합니다.

 

또한 이러한 조건을 통하여

3
-3 -2 -1
 
값 : -1
 
모두 음수일경우를 고려
https://www.acmicpc.net/board/view/87254

 

문제에서 유의해야할점은, 음수값이 나올 수 있기에

answer값이 = 0이 아닌 answer = arr[1]로 초기화하여 진행합니다.

 

 

위에처럼 dp[][] 배열을 나눠서 하지않고,

앞에서부터 DP1 값을 구하고 뒤에서부터 DP2 값을 구한뒤,

DP1[i-1] + DP2[i+1] 을 구함으로써 DP[i]를 제거한 값을 구할 수 있습니다.

 

 

코드

정답코드2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N;
	public static int[][] dp;
	public static int[] arr;
	public static int answer;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new int[N+1][2]; //[][0] : 아직 한번도 수를 제거하지않은경우, [][1] : 수를 한번 제거한경우
    	arr = new int[N+1];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=1;i<=N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	dp[1][0] = arr[1];
    	dp[1][1] = arr[1];
    	answer = arr[1];
    	for(int i=2;i<=N;i++) {
    		dp[i][0] = Math.max(arr[i], dp[i-1][0] + arr[i]); //특정수를 제거하지 않을 경우
    		dp[i][1] = Math.max(dp[i-2][0] + arr[i], dp[i-1][1] + arr[i]); // i번쨰 수를 제거하므로 dp[i-1][0]만 더해줍니다.
    	}
    	
    	for(int i=1;i<=N;i++) {
    		answer = Math.max(answer, Math.max(dp[i][0], dp[i][1]));
    	}
    	System.out.println(answer);
    	
    }
}

 

정답코드 1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N;
	public static int[][] dp;
	public static int[] arr;
	public static int answer;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new int[N+1][2]; //[][0] : 아직 한번도 수를 제거하지않은경우, [][1] : 수를 한번 제거한경우
    	arr = new int[N+1];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=1;i<=N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	dp[1][0] = arr[1];
    	dp[1][1] = arr[1];
    	answer = arr[1];
    	for(int i=2;i<=N;i++) {
    		dp[i][0] = Math.max(arr[i], dp[i-1][0] + arr[i]); //특정수를 제거하지 않을 경우
    		dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1] + arr[i]); // i번쨰 수를 제거하므로 dp[i-1][0]만 더해줍니다.
    	}
    	
    	for(int i=1;i<=N;i++) {
//    		System.out.println(dp[i]);
    		answer = Math.max(answer, Math.max(dp[i][0], dp[i][1]));
    	}
    	System.out.println(answer);
    	
    }
}

 

아래의 코드는 잘못되었다.

이유는 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다) 는 조건을 올바르게 구현하지 않았습니다.

아래와 같이 구현할경우 한번 이상 삭제할 가능성이 있기 떄문이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N;
	public static int[] dp;
	public static int[] arr;
	public static int answer;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new int[N+1];
    	arr = new int[N+1];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=1;i<=N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	dp[1] = arr[1];
    	for(int i=2;i<=N;i++) {
    		dp[i] = Math.max(arr[i], dp[i-1] + arr[i]);
    		dp[i] = Math.max(dp[i], dp[i-2] + arr[i]);
//    		System.out.println(dp[i]);
    	}
    	
    	dp[1] = arr[1];
    	for(int i=1;i<=N;i++) {
    		System.out.println(dp[i]);
    	}
    	
    }
}

 

기본 연속합 코드 (숫자 하나를 제거하는것을 고려하지 않은 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;
 
public class Main {
	public static int T, N, M;
	public static int answer = 0;
	public static int[] arr;
	public static int[] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	dp = new int[N];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	dp[0] = arr[0];
    	answer = dp[0];
    	for(int i=1;i<N;i++) {
    		dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
    		answer = Math.max(answer, dp[i]);
    	}
    	
    	System.out.println(answer);
    }
    
}