[백준]1932번 정수 삼각형 - C/C++

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

1932번: 정수 삼각형

문제

        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번째 줄까지 정수 삼각형이 주어진다.

출력

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

---

 

전형적인 dp 문제로 dp 배열에 해당 지점까지 올 수 있는 값들의 최대 합을 저장해두는 방식으로 자기 자신의 값과 dp 배열에서 대각선 왼쪽과 오른쪽 값 중 큰 값을 더해나가는 방식이다.

#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;
int N,ans =-1;
int arr[501][501] ={0};
int dp[501][501] = { 0 };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			cin >> arr[i][j];
			dp[i][j] = arr[i][j];
		}
	}
	ans = dp[0][0];
	for (int i = 1; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0)
				dp[i][j] += dp[i - 1][0];
			else if (j == i)
				dp[i][j] += dp[i - 1][j - 1];
			else
				dp[i][j] += max(dp[i-1][j - 1], dp[i-1][j]);

			if (i == N - 1)
				ans = max(ans, dp[i][j]);
		}
	}

	cout << ans;
	
	return 0;
}

---

    학기가 끝나서 오랜만에 포스팅을 한다. 저번 포스팅이 중간고사를 본 이후였는데 백준 문제를 풀 시간이 없을 정도로 전공 과목 6개에서 연속적으로 과제를 내주었다. 기말고사가 끝나고도 일주일 가량 기한을 더 주면서 까지 과제를 주는 과목들이 있어 종강이 굉장히 늦어졌다. 이제 진정한 방학이니깐 다시 백준 문제를 열심히 풀어야겠다!

    학기중에 코딩 테스트를 한번 봤는데 간단한 문제와 dfs 형식의 문제는 풀었지만 DP 문제는 DP로 풀어야 할 것 같다는 느낌만 받고 실제로는 풀지 못했다. 그래서 이번 방학 코딩의 시작을 산뜻하게 쉬운 DP문제를 선택하였다! 아무리 몇 달 동안 코딩을 안 했어도 다행히 실버 1 문제는 쉽게 풀렸다. 다만 제출하였을 때 N = 1 일 때 예외처리를 해주지 않아 한번 틀렸다. 틀렸다는 것을 안 뒤 금방 알아냈지만 만약 결과를 안 알려주는 코딩 테스트였다면 틀릴 뻔했다!