백준 1932번 :: 정수 삼각형 (Java)

문제 설명

백준 1932번: 정수 삼각형 (Silver 1)

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

문제 풀이

1. DP를 이용해 각 위치에 올 수 있는 경로의 최댓값을 찾는다.
2. 가장자리에 도착할 수 있는 경로는 하나뿐이므로 가장자리의 최댓값을 미리 구한다.
3. 나머지 위치에 대해서는 DP를 이용해 최댓값을 구한다.
   (각 위치는 왼쪽 상단 혹은 오른쪽 상단에서만 올 수 있음을 이용)
4. 마지막 층의 최댓값 중 가장 큰 값을 찾아서 출력한다.

소스 코드

소스 코드 링크

public static void main(String[] args) throws NumberFormatException, IOException {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = null;
	int n = Integer.parseInt(in.readLine());
	int map[][] = new int[n][n];
	for (int i = 0; i < n; i++) {
		st = new StringTokenizer(in.readLine(), " ");
		for (int j = 0; j <= i; j++) {
			map[i][j] = Integer.parseInt(st.nextToken());
		}
	}
	// 가장자리의 값 미리 구하기
	for (int i = 1; i < n; i++) {
		map[i][0] += map[i-1][0];
		map[i][i] += map[i-1][i-1];
	}
	// 현재 선택된 수의 대각선 왼쪽/오른쪽에서 선택
	for (int i = 2; i < n; i++) {
		for (int j = 1; j < i; j++) {
			map[i][j] += Math.max(map[i-1][j-1], map[i-1][j]);
		}
	}
	// 합이 최대가 되는 경로의 합
	Arrays.sort(map[n-1]);
	System.out.println(map[n-1][n-1]);
}

느낀 점

여전히 나에게 DP는 쉽지 않지만 이제 그래도 이런 기본적인 DP는 금방 생각할 수 있다. 갈 수 있는 곳이 둘이라는 건, 거기 올 수 있는 곳도 둘이라는 거니까! 맨 처음과 끝 값만 미리 채우고 각 위치는 바로 위층의 두 위치에 대한 값만 비교해서 최댓값 구하기~~~

사실 금방 풀어서 또 쉽게 생각하고 풀다가 실수 했을까봐 걱정했는데 다행히(?) 한 번에 맞았다😊 같은 DP 문제는 아니지만 아직 설명을 스스로 정리하지 못해서ㅠ 포스팅 못한 [백준] 16947. 서울 지하철 2호선 풀면서 자신감 너무 떨어졌었는데🥲 이번 문제 한 번에 풀고 나니까 그래도 그동안 공부한 게 헛된 건 아니다 싶고 자신감 조금 돌아왔다(?) 물론 이건 간단한 문제였지만 이렇게 계속 연습하고 공부 하다보면 좀 더 어려운 문제도 금방 풀 수 있게 되겠지?! 그렇게 되도록 열심히 해봐야지...ㅎ