[백준] code.plus(다이나믹 프로그램 part 2,JAVA)13398번, 연속합 2

문제 링크

13398번: 연속합 2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

다이나믹 프로그램

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

동적 계획법 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 감소하는 수열 중 가장 긴 수열의 길이를 결과로 출력해야 합니다.

 

배열

 

DP[][] : 메모이제이션 배열

 

sequence : 입력값 수열을 저장하는 배열

 

DP[][]와 sequence[] 배열을 이용하여 연속합이 가장 큰 값을 구하였습니다.

 

DP[i][0]의 값은 제거하지 않은 i번째 연속합의 최대값을 저장합니다.

DP[i][1]의 값은 하나의 값을 제거하고 i번째 연속합의 최대값을 저장합니다.

예제 입력1의 DP표를 표현하면

	10	-4	3	1	5	6	-35	12	21	-1
DP[i][0]	10	6	9	10	15	21	-14	12	33	32
DP[i][1]	0	10	13	14	19	25	21	33	54	53

DP[i][0]의 값들을 살펴보면서 규칙을 찾아보면

1. DP[i-1][0] ≥ 0일 때

DP[i][0] = DP[i-1][0] + sequence[i]

 

2. DP[i-1][0] < 0일 때

DP[i][0] = sequence[i]

 

예를 들어

DP[3][0]을 구할 때DP[3-1][0] = DP[2][0] = 6 ≥ 0으로DP[3][0] = DP[2][0] + sequence[3] = 6 + 3 = 9

 

DP[8][0]을 구할 때DP[8-1][0] = DP[7][0] = -14 < 0 으로DP[8][0] = sequence[8] = 12

 

DP[i][1]의 값들을 살펴보면서 규칙을 찾아보면

1. DP[i-1][1] + sequence[i] ≥ DP[i-1][0]일 때

DP[i-1][1] = DP[i-1][1] + sequence[i]

 

2. DP[i-1][1] + sequence[i] < DP[i-1][0]일 때

DP[i-1][1] = DP[i-1][0]

 

예를 들어

DP[3][1]을 구할 때

DP[3-1][1] + sequence[3] = DP[2][1] + sequence[3] = 10 + 3 = 13 ≥ 10(DP[2][0])으로

DP[3][1] = DP[2][1] + sequence[3] = 10 + 3 = 13

 

DP[7][1]을 구할 때

DP[7-1][1] + sequence[7] = DP[6][1] + sequence[7] = 25 + (-35) = -10 < 21(DP[6][0])으로

DP[7][1] = DP[6][0] = 21

 

참고.

DP[i-1][1] + sequence[i] < DP[i-1][0]일 때

DP[i-1][1] = DP[i-1][0]의 규칙이 나온 이유는

 

DP[i][0]의 값은 수열의 값을 하나도 제거하지 않은 최대 연속합이고 DP[i][1]은 하나를 제거한 상태인데

DP[i-1][0]이 더 크다는 것은 하나를 제거를 하고 연속합을 구했을 때에도 제거하지 않았을 때보다 작아지는 현상이 발생되면 하나도 제거되지 않은 상태에서 그 값을 제거하는 형태로 변경한다는 뜻입니다.

 

예를 들어

DP[6][1]일 때에는 10 + 3 + 1 + 5 + 6 = 25로 -4를 제외한 형태입니다.

DP[6][0]일 때에는 10 + (-4) + 3 + 1 + 5 + 6 = 21입니다.

 

DP[7][1]을 구할 때 그대로 더한다면 -10이 되어 하나를 제거했음에도 연속합이 더 작아지는 현상이 발생합니다.

그래서 DP[6][0]은 -4를 제외하지 않은 상태에서 해당 값 -35를 제거하는 형태로 바꿉니다.

DP[7][1] = DP[6][0]의 형태로 바뀐다는 것은 결과적으로

10 + 3 + 1 + 5 + 6 + (-35)= -10가 아닌

10 + (-4) + 3 + 1 + 5 + 6 = 21의 형태로 바꾸어 주는 것입니다.

 

결과로 DP[][]값 중에서 가장 큰 값을 출력합니다.

 

가장 큰 값 54가 결과로 출력합니다.

 

문제에 해결알고리즘은

1. DP[1][0]의 값을 sequence[1]으로 초기화해줍니다.

2. 규칙을 적용하여 DP[][]를 구성합니다.

3. 입력된 수열 값이 1개일 때에는 그 값을 출력하였습니다.

4. 2개 이상일 때에는 DP의 최대값을 구해서 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer을 통해 입력되는 수열 값을 분리하였습니다.
• DP[1][0]의 값을 sequence[1]로 초기화해주었습니다.
• 규칙을 적용하여 DP를 구성하고 최대 연속합을 반환하는 cal함수를 만들었습니다.
• BufferedWriter에 입력된 수열 값이 1개일 때에는 해당 수열 값을 저장하였습니다.
• BufferedWriter에 입력된 수열이 여러개인 경우 최대 연속합을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• cal은 반복문을 통해 위에 설명한 규칙을 적용시켜주었습니다.
• cal은 DP를 구성하고난 뒤에 최대 연속합을 결과로 반환하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int n,result;
	static int[] sequence;	//입력된 수열의 값 저장 배열
	static int[][] DP;		//메모이제이션 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //--------입력값 저장 및 배열 초기화--------
    	n = Integer.parseInt(br.readLine());
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	sequence = new int[n+1];
    	DP = new int[n+1][2];
    	for(int i=1;i<=n;i++)
    		sequence[i] = Integer.parseInt(st.nextToken());
    	DP[1][0] = sequence[1];	//DP[1][0]을 sequence[1]로 초기화
    	if(n==1)		//입력된 수열 값이 1개일 때 그 값 그대로 출력
    		result = sequence[1];
    	else		//DP구성하는 함수 실행
    		result = cal();
    	bw.write(result + "\n");		//최대 길이 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //반복문을 통해 규칙을 적용하여 DP 구성 및 최대 연속합 구하는 함수
    static int cal() {
    	int max = Integer.MIN_VALUE;	//최대값 초기화
    	for(int i=2;i<=n;i++) {
    		if(DP[i-1][0]>=0) 	//DP[i][0]의 규칙1.
    			DP[i][0] = DP[i-1][0] + sequence[i];
    		else		//DP[i][0]의 규칙2.
    			DP[i][0] = sequence[i];
    		
    		if(DP[i-1][1] + sequence[i] >= DP[i-1][0])	//DP[i][1]의 규칙1.
    			DP[i][1] = DP[i-1][1] + sequence[i];	
    		else		//DP[i][1]의 규칙2.
    			DP[i][1] = DP[i-1][0];
    		
    		max = Math.max(max, Math.max(DP[i][0], DP[i][1]));	//최대값 비교
    	}
    	return max;		//최대 연속합 반환
    }
}