[백준,BOJ 1912] 연속합(JAVA 구현,추가풀이)

 

-내 생각

  문제를 제대로 읽어보지 않아서 점화식을 세울 수가 없었다. 이 문제에서 중요하게 보아야 할 내용은 수를 선택할 때 한 개 이상의 수를 연속되게 선택해야 한다는 제약조건이 있다. 즉 1번 숫자를 선택한 후 2번 숫자를 선택하지 않으면 더 이상 선택할 수 가없는 것이다. 

 

-해법

  그렇다면 이 문제는 어떻게 해결해야 할까? 별도의 dp배열을 생성하여 누적된 값과 현재부터 다시 선택을 시작한 값을 비교해주면 간단하다. 우선 기본적인 점화식은 dp [n] = dp [n-1] + cost [n]이 되는데(기본 누적 점화식), 연속해서 선택해야 한다는 제약조건이 존재하기 때문에 예를 들어, 2번까지 누적해서 선택한 결과와 2번이 첫 번째로 선택된 결과 중 큰 값을 취해야 한다는 것인데, 1번, 2번을 누적하게 되면 누적 값은 6이 되고, 2번이 첫 번째로 선택되는 경우는 -4가 된다. 6>-4가 되므로 dp [n] = 6이 되는 것이다. 이와 같은 과정으로 예제 입력을 진행하면 아래의 표와 같은 dp 배열이 만들어진다.

 

10	-4	3	1	5	6	-35	12	21	-1
10	6(>-4)	9(>3)	10(>1)	15(>5)	21(>6)	-14(>-35)	12(>-2)	33(>21)	32(>-1)

  이제 완성된 dp배열에서 최댓값을 찾게 되면 만들 수 있는 연속 합의 값이 구해지게 되는 것이다.

 

import java.util.*;

public class Main {
	static int n; // N 변수
	static int dp[],cost[]; // 메모이제이션 배열과 각 값을 저장 할 배열
	
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		dp = new int[n+1];
		cost = new int[n+1];
		
		for(int i=1;i<=n;i++) { // 각 값을 입력
			cost[i] = sc.nextInt();
		}
		
		dp[1] = cost[1]; // dp 1번 인덱스의 경우는 자기 자신밖에 될 수 없다.
		for(int i=2;i<=n;i++) { // dp 1번 인덱스가 초기화 되어 있으므로 2번 인덱스부터 탐색 시작
			dp[i] = Math.max(dp[i-1]+cost[i], cost[i]); // 자기 자신과 이전까지 누적값 + 자기자신의 값 중 큰 값을 취한다.
		}
		
		int max =Integer.MIN_VALUE;
		for(int i=1;i<=n;i++) {
			if(dp[i] > max)
				max = dp[i];
		}
		
		System.out.println(max); // 완성된 dp 배열에서 최댓값을 찾아 출력
		
	}
	
}

---

  이 문제를 다시 풀었을 때, 이전의 풀이 방법이 아닌 다른 방식으로 풀었다. 숫자를 합하는 경우의 수를 따져보면 총 3가지가 존재한다.

 

  1. 이전의 숫자는 선택하지 않고 자신만 선택한 경우.

  2. 자신 이전의 숫자부터 시작해 자신도 선택한 경우.

  3. 자신 이전의 숫자까지 누적되어 온 값에 이어 자신 또한 선택한 경우.

 

  이 세 가지의 경우에서 최댓값을 찾아 dp에 저장해 나간 후, dp에서 최댓값을 찾으면 된다.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		
		int a[] = new int[n];
		int dp[] = new int[n];
		
		// 데이터 입력
		for(int i=0;i<n;i++) {
			a[i] = in.nextInt();
		}
		
		// 누적합을 저장하는 dp 배열에 0번 인덱스 값을 초기화
		dp[0] = a[0];
				
		// 1번 인덱스부터 시작
		for(int i=1;i<n;i++) {
			// 누적합으로 오는 경우는 1. 자신부터 선택 시작 2. 자신 이전부터 선택 시작 3. 자신 이전까지 누적되어온 값에 이어 선택
			// 이 중 최댓값을 저장하면 된다. 
			dp[i] = Math.max(Math.max(a[i], dp[i-1]+a[i]),a[i] + a[i-1]);
		}
		
		// 최댓값을 찾아 출력
		int max = Integer.MIN_VALUE;
		
		for(int i=0;i<n;i++) {
			if(dp[i]>max)
				max = Math.max(max, dp[i]);
		}
		
		System.out.println(max);
		
		in.close();
	}

}