JUST WRITE IT. HomeArchivesTagsCategories
백준 1932번 정수 삼각형
|AlgorithmBOJ|

#1932. 정수 삼각형

문제링크

Problem

  • 맨 위층부터 시작 → 맨 아래 층
    선택된 수들을 합하면서 내려옴
  • 현재 층에서 선택된 수의 대각선(왼 or 오)만 가능
  • condition
    • 층은 최대 500
    • 수의 범위 0~9999
  • Goal : 합이 최대가 되는 수

Solution

  • 입력을 보면 알겠지만 자기 자신 바로 아래와 오른쪽만 가능
    1
    2
    3
    4
    5
    6
    // input
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
  • 그냥 재귀함수를 쓰면 반복되는 호출이 많이 일어난다.
    DP를 사용해야 함을 알 수 있다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // #0
    7
    // #1
    7+3 / 7+8
    // #2
    7+3+8, 7+3+1 / 7+8+1, 7+8+0
    // #3
    7+3+8+2, 7+3+8+7 / 7+3+1+7, 7+3+1+4 / 7+8+1+7, 7+8+1+4 / 7+8+0+4, 7+8+0 +4
    // #4
    20+4, 20+5 / 25+5, 25+2 / 18+5, 18+2 / 14+2, 14+6 / 23+5, 23+2 / ...
    경우의 수는 1→2→4→8→16으로 늘어난다.

500일 때 최대 500^2 = 250000(25만)의 경우의 수가 나온다. 물론 재귀함수를 사용하면 이보다 더 많은 함수 호출이 일어나 시간초과가 발생할 것이다.

6개월 전에 풀었던 것을 다시 풀어보려니…생각이 안난다.

dp[a][b]

1 Try (6개월 전 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
using namespace std;
int t[500][500];
int d[500][500];
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++)
		{
			cin >> t[i][j];
		}
	}
	d[0][0] = t[0][0];
	for (int k = 1; k < n; k++)
	{
		for (int h = 0; h < n; h++)
		{
			if (h == 0)
			{
				d[k][0] = d[k - 1][0] + t[k][0]; //바로 위의 최대경로만 가져올 수 있음.
			}
			else if (k == h)
			{
				d[k][h] = d[k - 1][h - 1] + t[k][h]; // 바로 위 왼쪽의 최대경로만 가져올 수 있음.
			}
			else {
				d[k][h] = max(d[k - 1][h - 1], d[k - 1][h]) + t[k][h];
			}
		}
	}
	int max_cost = 0; // 0보다 작을 수 없음.
	for (int index = 0; index < n; index++)
	{
		max_cost = max(d[n - 1][index], max_cost);
	}
	cout << max_cost << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int max_sum = 0;
vector<vector<int>> dp;
int main() {
   int n, input;
   scanf(" %d", &n);
   dp.resize(n);
   vector<vector<int>> tri(n);
   for(int i = 0; i < n; ++i) {
      for(int j = i; j >= 0; --j) {
         scanf(" %d", &input);
         tri[i].push_back(input);
      }
   }
   dp[0][0] = tri[0][0];
   for(int i = 1; i < n; ++i) {
      for(int j = 0; j <= i; ++j) {
         dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]);
      }
   }
   
   cout << max_sum << endl;
   return 0;
}
Algorithm