[백준] 1912번 : 연속합 - JAVA [자바]

www.acmicpc.net/problem/1912

1912번: 연속합

 

---

• 문제

 

 

 

 

 

이 문제는 너무 쉬운 문제라.. 메모이제이션하면서 구간만 잘 찾아내면 끝인 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

꽤나 쉬운 문제임에도 정답 비율이 꽤나 낮은 문제다. 아마 '연속 되는 수를 선택'해야 한다는 조건을 놓치거나 음수를 빼버리는 경우? 이렇게 접근해서 틀린 분들이 많지 않을까 싶다.

 

문제 예제들을 그대로 적용해보면 이렇다.

 

첫 번째 예제는 아래와 같다. (배열로 표현함)

 

여기서 연속된 수를 선택하여 뽑아내면 다음과 같다.

 

 

첫 번째 예제는 쉬울 것이다.

 

 

두 번째 예제를 보자.

 

 

 

두 번째 예제를 보면 index5 에 -4 라는 음수가 들어있지만 이를 포함하여 index7까지 연속으로 택하여 합한 것이 최댓값임을 알 수 있다.

 

즉, 포인트는 음수 양수 상관없이 '연속적으로 선택한 수의 합'이 최댓값이 되는 수를 찾으면 되는 것이다. 즉, 메모이제이션은 이전까지 탐색했던 값과 현재 위치의 값을 비교하여 큰 값을 저장하면 되는 것이다.

 

 

Top-Down 방식인 재귀로 구현하자면 개괄적으로 다음과 같다.

 

static int recur(int N) {

	// 탐색하지 않은 인덱스라면
	if(dp[N] == null) {

		// (이전 배열의 누적합 + 현재 값)과 현재 값을 비교하여 최댓값을 N위치에 저장
		dp[N] = Math.max(recur(N - 1) + arr[N], arr[N]);
		
	}
		
	return dp[N];
}

 

 

 

반대로 Bottom-Up으로 하면 위 코드를 반복문으로 다음과 같이 구현할 수 있다.

 

for (int i = 1; i < N; i++) {
	dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
}

 

 

그러면 메모이제이션이 된 dp배열에는 각 인덱스까지의 최댓값이 저장되어있다는 의미다. 예로들어 dp[3]이라 하면 dp[0] ~ dp[3] 에서 연속으로 선택한 부분 수열의 최댓값이 저장되어있다는 의미다.

 

그리고 나서 dp 배열의 원소들 중 가장 큰 값을 찾아서 출력하면 되는 것이다.

 

 

이 때 dp배열의 최댓값을 정렬 또는 하나하나 탐색하여 찾아내는 방법도 있지만, 처음부터 아예 재귀 또는 반복문안에 max변수를 하나 두어 최댓값을 갱신 하는 것이 더욱 효율적일 것이다. 말로하면 어려우니 자세한 것은 코드를 보면서 이해해보도록 하자.

 

 

 

 

 

 

 

 

 

---

• 4가지 방법을 사용하여 풀이한다.

 

 

여느때와 마찬가지로 각 알고리즘(Top-Down, Bottom-Up)과 입력방법을 조합하여 각각의 성능을 비교해보고자 한다.

 

1 . Scanner + Top-Down

2. BufferedReader + Top-Down

3 . Scanner + Bottom-Up

4. BufferedReader + Bottom-Up

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + Top-Down]

 

import java.util.Scanner;

public class Main {
	
	static int[] arr;		// 배열 
	static Integer[] dp;		// 메모이제이션 할 dp
	static int max;			// 최댓값 변수 
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		arr = new int[N];
		dp = new Integer[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
		
		/*
		 * dp[0]은 첫 원소로 이전에 더이상 탐색할 것이 없기 때문에
		 * arr[0] 자체 값이 되므로 arr[0]으로 초기화 해준다.
		 * max또한 첫 번째 원소로 초기화 해준다.
		 */
		dp[0] = arr[0];
		max = arr[0];
		
		// dp의 마지막 index는 N-1이므로 N-1부터 Top-Down 탐색 
		recur(N - 1);
		
		System.out.println(max);
	}
	
	static int recur(int N) {
		
		// 탐색하지 않은 인덱스라면
		if(dp[N] == null) {
			dp[N] = Math.max(recur(N - 1) + arr[N], arr[N]);

			// 해당 dp[N]과 max 중 큰 값으로 max 갱신 
			max = Math.max(dp[N], max);
		}
		
		return dp[N];
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

앞서 말했듯 탐색 과정에서 아예 max변수를 두고 해당 index n의 위치에 저장 될 최댓값과 현재 max값을 비교하면서 최댓값을 갱신시키는 것이다. 이렇게 하는 것이 굳이 recur() 탐색 종료 후 또 dp배열을 탐색하면서 최댓값을 찾을 필요 없이 recur() 탐색 과정에서 한 번에 처리할 수 있으니 좀 더 효율적이다.

 

 

 

---

- 방법 2 : [BufferedReader + Top-Down]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 알고리즘은 방법 1과 똑같으니 크게 어렵지 않을 것이다.

 

 

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

public class Main {
	
	static int[] arr;		// 배열 
	static Integer[] dp;	// 메모이제이션 할 dp
	static int max;			// 최댓값 변수 
	
	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];
		dp = new Integer[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		/*
		 * dp[0]은 첫 원소로 이전에 더이상 탐색할 것이 없기 때문에
		 * arr[0] 자체 값이 되므로 arr[0]으로 초기화 해준다.
		 * max또한 첫 번째 원소로 초기화 해준다.
		 */
		dp[0] = arr[0];
		max = arr[0];
		
		// dp의 마지막 index는 N-1이므로 N-1부터 Top-Down 탐색 
		recur(N - 1);
		
		System.out.println(max);
	}
	
	static int recur(int N) {
		
		// 탐색하지 않은 인덱스라면
		if(dp[N] == null) {
			dp[N] = Math.max(recur(N - 1) + arr[N], arr[N]);

			// 해당 dp[N]과 max 중 큰 값으로 max 갱신 
			max = Math.max(dp[N], max);
		}
		
		return dp[N];
	}
}

 

 

 

크게 어려울 것은 없을 것이다. 이번 문제는 중복을 고려하지 않아도 되니 오히려 쉬웠을 수도 있다.

 

 

 

 

---

- 방법 3 : [Scanner + Bottom-Up]

 

 

 

반복문으로 풀어본 방식이다.

 

 

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		
		int[] arr = new int[N];
		int[] dp = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
		

		/*
		 * dp[0]은 첫 원소로 이전에 더이상 탐색할 것이 없기 때문에
		 * arr[0] 자체 값이 되므로 arr[0]으로 초기화 해준다.
		 * max또한 첫 번째 원소로 초기화 해준다.
		 */
		dp[0] = arr[0];
		int max = arr[0];
		
		for (int i = 1; i < N; i++) {
			// (이전 dp + 현재 arr값) 과 현재 arr값 중 큰 것을 dp에 저장 
			dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
			// 최댓값 갱신 
			max = Math.max(max, dp[i]);
		}
		System.out.println(max);

	}
}

 

 

 

크게 어려울 것은 없을 것이다. 필자 생각으론 이 문제가 좀 더 앞순번에 있어야 했지 않았을까... 생각이 든다.

 

 

 

---

- 방법 4 : [BufferedReader + Bottom-Up]

 

 

 

 

이 방법이 아마 가장 효율적일 것이다. 방법 3에서 Scanner 대신 BufferedReader을 사용한 방법이다.

 

 

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

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

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		

		/*
		 * dp[0]은 첫 원소로 이전에 더이상 탐색할 것이 없기 때문에
		 * arr[0] 자체 값이 되므로 arr[0]으로 초기화 해준다.
		 * max또한 첫 번째 원소로 초기화 해준다.
		 */
		dp[0] = arr[0];
		int max = arr[0];
		
		for (int i = 1; i < N; i++) {
			// (이전 dp + 현재 arr값) 과 현재 arr값 중 큰 것을 dp에 저장 
			dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
			// 최댓값 갱신 
			max = Math.max(max, dp[i]);
		}
		System.out.println(max);

	}
}

 

 

 

오버헤드가 적어서(애초에 재귀 자체가 호출 할 때마다 메소드 자체를 로드하기 때문에 오버헤드가 크다) 이 방법이 시간이나 메모리 측면에서 좀 더 효율적일 것이다. (성능이 좋다는 의미)

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 22457053  -  방법 4 : BufferedReader + Bottom-Up

채점 번호 : 22457048  -  방법 3 : Scanner + Bottom-Up

채점 번호 : 22457041  -  방법 2 : BufferedReader + Top-Down

채점 번호 : 22457029  -  방법 1 : Scanner + Top-Down

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다. 입력되는 시퀀스 원소가 최대 10만개라 더 두드러져 보이는 듯 하다. 그리고 앞서 말했듯 Bottom-Up방식이 좀 더 효율적인 것을 볼 수 있다.

---

• 정리

 

아마 문제를 잘 보고 풀었다면 금방 해결 할 수 있는 문제였을 것이다. 동적계획법 문제를 은근 어려워 하는 분들이 많은데(특히 Top-Down) 가장 쉽게 푸는 방법은 수식의 점화식을 먼저 구하는 것이다. 점화식만 구하면 재귀로 쉽게 구현할 수 있고, Bottom-Up으로도 쉽게 변환할 수 있다.

 

물론 점화식을 구하는 것이 어려울 수는 있다만, 좀 더 큰 그림을 보고 어떠한 조건들이 필요한지 찾으면 금방 점화식을 찾아낼 수 있으니 바로바로 떠올릴 수 있도록 연습을 하는 것이 중요할 것이다.

 

 만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.