백준(BOJ) 1932: 정수 삼각형

정수삼각형: https://www.acmicpc.net/problem/1932

기타리스트: https://www.acmicpc.net/problem/1495

 

 

정수삼각형문제는 최종 결과값들을 조회할 수 있는 틀이 있다. 하지만 기타리스트 문제는 최종 결과값들을 조회할 수 있는 정수삼각형 문제에서말하는 그 틀이 없고 입력으로 주워지는 최댓값이 있어 제한될 수 있는 범위라는 것이 있고 그 범위를 조회하면 답이 구해진다. 

위에서 말하는 정수 삼각형 문제에서 틀이라는 것은 아래 그림과 같이 1,2,3,4,5...n 행을 거치는 누적 값들이 결국은 최하위행의 열중 어느 하나의 열에 결국은 들어가게 된다는 것이다. 기타리스트 문제는 이런 틀이 없다. 다만 결과로 얻을 수 있는 값을 제한하고 그로부터 조회할 수 있는 값의 범위는 매우  제한적이되어 그 범위만을 탐색하여 답을 구할수 있다. 

두 문제의 공통점은 모두 중간의 과정들을 모두 빠짐없이 거쳐야만 하고 그 과정을 거치면서 값이 누적되어 간다는 것이다. 

-------------------------------------------------------------------문제 해설--------------------------------------------

출처: https://www.youtube.com/watch?v=jfKfPfyJRdk   (글의 모호한 부분 아랫글에서 모두 수정)

  이번 문제 이전에 풀었던 RGB거리 문제 덕에 이러한 비용 문제, 또는 숫자의 누적 문제는 문제에서 주어진 입력과 동일하게 배열을 하나 만들어 해당하는 지점까지의 결과를 저장해 나가면서 풀면 된다는 것을 알 수 있었다.

  이 문제에서 약간 혼동될 수 있는 부분이 있다고 생각하는데, 문제 부분의 글과 그림을 보면 정삼각형의 형태로 입력이 주어지는 것처럼 보이지만, 예제 입력 1을 보면 알 수 있듯이 열이 +1씩 되면서 입력이 되는 것을 알 수 있다. 그렇기 때문에 문제에서 말하는 (아랫방향의)왼쪽 대각선과 오른쪽 대각선의 의미는 사실상 배열의 개념에서 생각해 볼 때, (다음행의)자신과 같은 열과 그다음 열을 의미한다는 것이다. 예를 들어, 삼각형의 2층에서 8이 선택할 수 있는 숫자는 바로 아래 행에서 자신이 위치한 열인 1과, 그다음 열인 0인 것이다.

-해법

  위에 언급했듯이 입력과 동일한 배열은 만들면 된다는 것을 알게 되었다. 그렇다면 그 배열에 누적된 값들은 어떠한 방식으로 저장해주어야 할까? 실제로 해당 삼각형의 누적된 모습을 노트에 그려보면 1번 열에 속한 값들은 모두 이전의 행값 + 자신의 값이라는 것을 알 수 있다. 예를 들어 2층부터 3의 자리에 누적될 값은 같은 열이면서 이전행의 값인 7+ 자신의 값 3으로 10이 되는 것이다. 이러한 현상이 발생하는 이유는 위에서 서술했듯, 자신이 속한 열과 그 다음열만을 선택할 수 있기 때문인데, 1번 열의 경우에는 자신이 속한 열을 제외하고는 이전의 행의 다른 열로부터 영향을 받을 수가 없기 때문이다.

  하지만 1번 열을 제외하고는 상황이 달라진다. 왜냐하면 이전 행의 이전열로부터 영향을 받기 때문인데, 예를 들어 3층의 1번 값에 누적될 결과는 (2층의 3번에 누적된 값 + 자신의 값) 또는 (2층의 8번에 누적된 값 + 자신의 값) 중 큰 값을 골라야 한다.

 

  위의 내용을 요약해 점화식을 세워보면 (I는 행, J는 열, DP는 누적값 저장 배열, COST는 입력값 저장 배열)

 

if(j==1)  // 1번 열의 경우
   dp[i][j] = cost [i][j]+ dp [i-1][j];  // 자신의 값 + 자신이 속한 열의 이전 행까지 누적된 값
else  // 2 ~ N번 열의 경우
   dp[i][j] = cost [i][j] + Math.max(dp[ i - 1 ][ j - 1 ], dp [ i - 1 ][ j ]);

(마지막 열 같은 경우 어차피 자신의 윗쪽 오른쪽 방향의 값은 0이라서 따로 처리해 줄 필요없음)

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();
		
        // 1번 인덱스부터 사용하기 때문에 +1
		dp = new int[n+1][n+1];
		cost = new int[n+1][n+1];
		
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=i;j++) { // i의 값에 따라 열의 수를 조정해준다.
				cost[i][j] = sc.nextInt();
			}
		}
		
		
		dp[1][1] = cost[1][1]; // 최상층 값은 미리 누적값에 저장해둔다.
		
		for(int i=2;i<=n;i++) { // 최상층의 아래층 부터 n까지 반복
			for(int j=1;j<=i;j++) { // 1번열부터 i까지 반복, i가 2일 경우 2까지 3일 경우 3까지...
				// 점화식
                if(j==1)
					dp[i][j] = cost[i][j]+ dp[i-1][j];
				else
					dp[i][j] = cost[i][j] + Math.max(dp[i-1][j], dp[i-1][j-1]);
			}
		}
        
		int max = Integer.MIN_VALUE;
		for(int i=1;i<=n;i++) { // n층에 저장 된 값들 중 최댓값을 찾으면 된다.
			if(dp[n][i]>max) {
				max = dp[n][i];
			}
		}
		
		System.out.println(max);	
		
	}
	
}

---

 작은 문제부터 결과를 도출해내는 방식이므로 굳이 dp 배열을 사용할 필요가 없다. 왜냐하면 데이터로 주어지는 값이 있기 때문에 그 값들을 경신시키면서 사용하면 된다.

  그렇기에 문제를 푸는 기본 개념은 이전의 풀이와 큰 차이가 없지만, 코드상으로는 쓸데없는 dp배열을 사용하지 않고 표현할 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Testing3 {

    public static void solution(int n, int[][]dp){
        for(int i=2;i<=n;++i){
            for(int j=1;j<=i;++j){
                if(j==1)
                    dp[i][j]+=dp[i-1][j];
                else{
                    dp[i][j]=dp[i][j]+Math.max(dp[i-1][j-1], dp[i-1][j]);
                }
            }
        }
        int maxValue=Integer.MIN_VALUE;
        for(int i=1;i<=n;i++)
            maxValue=Math.max(dp[n][i], maxValue);

        System.out.println(maxValue);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n=Integer.parseInt(br.readLine());
        int[][]arr=new int[n+1][n+1];
        for(int i=1;i<n+1;++i) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= i; ++j)
                arr[i][j] = Integer.parseInt(st.nextToken());
        }
        solution(n, arr);
    }
}

  즉, a[i][j] += Math.max(a [i-1][j] , a [i-1][j-1]); 과 같은 수식은 가장 작은 문제(가장 낮은 행, 결과로 부터 가장 먼 경우)부터 문제를 고려하기 시작하게 되는데 그 과정에서 필요한 Math.max(a [i-1][j] , a [i-1][j-1])의 값들은 이미 이전부터 저장해 오면서 올라가기 때문에 별도의 dp배열을 사용할 필요가 없다는 의미이다.