[Baekjoon] 1932번: 정수 삼각형

 

 

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

1932번: 정수 삼각형

 

---

 

문제 해결 과정

착안

처음 착안에서 크기 $N$의 정수 삼각형을 구성하는 수들을 모두 입력받은 다음, 삼각형의 가장 아래 층부터 인접한 숫자끼리 비교하여 큰 숫자를 위 층의 숫자에 더하는 방식으로 구현하고자 하였다(동적계획법, dynamic programming).

 

문제를 해결한 뒤, 계산하고 난 다음에는 사용되지 않는 숫자 층들을 모두 저장하지 않고 메모리 공간을 절약해보고자, 숫자를 입력받는 순서대로 계산을 수행(위층에서부터 아래층으로 순차적 계산)하는 코드도 작성해보고자 하였다.

 

구현

전자의 경우는 코드 상으로는 훨씬 더 간편하게 구현할 수 있는데, 입력받는 순서대로 숫자를 계산하는 경우는 저장하는 배열을 최소화하여 구현하고자 하였으므로 계산 순서에 주의하여 구현하였다.

* 위층의 $i$ 번째 숫자($2 \leq i \leq N-1$)는 아래층 $i, (i+1)$ 번째 숫자를 계산할 때 즉, 두 번 사용되어야 하기 때문.

 

[스포 주의] (코드 1: 전체 삼각형을 입력받은 다음 아래층부터 누적) 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

// 코드 1: 전체 삼각형을 저장한 다음 아래층부터 위층 순으로 메모이제이션

#include <iostream>

using namespace std;

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

	int N;
	cin >> N;

	int Nums[500][500];

	for (int i = 0; i < N; i++)
		for (int j = 0; j < i + 1; j++)
			cin >> Nums[i][j];

	for (int i = N - 1; i > 0; i--)
		for (int j = 0; j < i; j++)
			Nums[i - 1][j] = Nums[i - 1][j] + (Nums[i][j] > Nums[i][j + 1] ? Nums[i][j] : Nums[i][j + 1]);

	cout << Nums[0][0];

	return 0;
}

 

[스포 주의] (코드 2: 수를 입력받는 순서로 메모이제이션) 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

// 코드 2: 입력받는 순서대로, 위층부터 아래층 순으로 메모이제이션

#include <iostream>

using namespace std;

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

	int N;
	cin >> N;

	int max = 0;
	int Nums[500] = { 0, };
	for (int i = 0; i < N; i++)
	{
		for (int j = i; j >= 0; j--)
		{
			int num;
			cin >> num;
			if (j == 0)
				Nums[j] += num;
			else if (j == i)
				Nums[j] = Nums[j - 1] + num;
			else
				Nums[j] = num + (Nums[j - 1] > Nums[j] ? Nums[j - 1] : Nums[j]);

			max = max < Nums[j] ? Nums[j] : max;
		}
	}

	cout << max << "\n";

	return 0;
}

 

실행 결과

위: 입력받는 순서대로 계산하여 메모리를 절약한 결과, 아래: 전체 수를 입력받은 뒤 삼각형의 아래부터 계산한 결과