백준 2228번 자바 ☆☆

문제

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

2228번: 구간 나누기

import java.util.Scanner;

public class Main {

	static int N,M;
	static int[] arr;
	static int[] sum;
	static int[][] dp;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		arr = new int[N+1];
		sum = new int[N+1];
		dp = new int[M+1][N+1];
		
		for (int i=1; i<=N; i++) {
			arr[i] = sc.nextInt();
		}
		
		sum[1] = arr[1];
		for (int i=2; i<=N; i++) {
			sum[i] = sum[i-1] + arr[i];
		}
		
		for (int i=1; i<=M; i++) {
			for (int j=0; j<=N; j++) {
				dp[i][j] = Integer.MIN_VALUE/2;
			}
		}

		dp[1][1] = arr[1];
		for (int i=1; i<=M; i++) {
			for (int j=2; j<=N; j++) {
				dp[i][j] = dp[i][j-1];
				
				int min = 0;
				if (i == 1) {
					min = -1;
				}
				for (int k=j-2; k>=min; k--) {
					if (k < 0) {
						dp[i][j] = Math.max(dp[i][j], sum[j]);
					} else {
						dp[i][j] = Math.max(dp[i][j], dp[i-1][k] + (sum[j] - sum[k+1]));
					}
				}
			}
		}
		
		System.out.println(dp[M][N]);
	}
}

1. 문제 풀이에 대한 자세한 내용은 아래 타 블로그 주소를 첨부했다.

 

2. 해당 문제를 풀며 헤맸던 부분을 추가로 작성한다.

 첫째, 문제에 대한 이해도.

 문제 내용이 애매한건지 내 문해력이 낮은건지는 잘 모르겠다. 다만 문제 내용중 '각 구간은 한 개 이상의 연속된 수들로 이루어진다.' 이 부분이 1,2,3,4처럼 연속된 정수로 이루어진다고 이해했다. 그러다보니 문제에 대하 접근자체가 완전히 엉뚱한 길로 들어가고 체감 난이도가 높아졌다.

 

 둘째, dp[i][j]의 초기값은 왜 Integer.MIN_VALUE/2 일까?

 먼저 N의 최대 길이는 100, 배열 N의 각 원소들의 값은 -32768 ~ 32767 사이의 정수다. 그렇다면 각 배열의 원소가 모두 -32768일 경우 가장 작은 구간합은 -32768 * 100이 된다. 그렇기에 넉넉하게 Integer.MIN_VALUE/2로 초기값을 설정한 것이다. 그렇다면 왜 2로 나눴을까? 점화식에서 오버플로우가 발생할 수 있기때문이다. 이 부분을 이해하는데 많이 헤맸다.

 

 셋째, dp[i][j] 초기화 시 왜 j는 0부터 시작할까?

 j값이 1부터 시작한다면 j=0일때 dp[i][j]는 당연히 0으로 초기화 될 것이다. 하지만 j=0이라는 뜻은 M개의 구간에서 N이 하나도 없는 경우이다. 구간합이 0이 될수도 있기 때문에 N이 하나도 없는 경우는 Integer.MIN_VALUE/2로 초기화 되어야 이후 점화식에서 올바른 답이 도출 될 수 있다.  

 

정리 : 문제이해도부터 해답을 찾는 과정까지 쉽지 않았다. 오랜만에 어떻게 해야할지 감이 전혀 안잡혔던 문제다. 또 다른 블로그들의 코드를 봐도 명확하게 이해가 되지 않았다. 다음번에 꼭 다시 풀어봐야하는 문제다.

 

 

참고 및 출처 : https://lotuslee.tistory.com/116