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

문제

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

1932번: 정수 삼각형

 

문제이해

• 첫째 줄에 삼각형의 높이 n을 입력한다.
• 두 번째 줄부터 n개의 줄동안 높이가 n인 삼각형을 입력한다.
• 층마다 선택한 수의 합 중 최댓값을 출력한다.

삼각형의 각 층에서 한개씩의 숫자를 골라 합을 저장하며 마지막 층까지 내려갔을 때 합들 중에서 최댓값을 찾아 출력하면 된다.

각 층에서 나올수있는 합들을 배열에 저장하고 다음 층에서 저장해 놓았던 배열에 전에 했던 것과 마찬가지로 그 층의 수들을 더하는 과정을 반복하면 된다.

다만 이 문제에서 각 층마다 숫자를 고르는데에는 규칙이 있다. 자신의 아래층에서 대각선 왼쪽 또는 대각선 오른쪽에 있는 숫자만 선택할 수 있다. 이 규칙에 대해서 주의해야 할 점이 하나 있다. 삼각형의 일부분을 가지고 설명하겠다.

  3  8   (1층)
8  1  0 (2층)

1층의 3의 경우 8이나 1을 더할수있고, 1층의 8의 경우 1이나 0을 더할 수 있다. 총 4개의 결과가 있고 이를 나열해 보면 (11 4 9 8)이다. 여기서 4와 9는 1을 더해서 나온 수이다. 이 문제에서는 마지막 층까지의 한중 최댓값을 구하고자 하는 것이기 때문에 4의 경우 필요가 없는 수가 된다. 따라서 2층까지의 합을 나열할 땐 (11 9 8)만 나열하면 된다.

 

다음은 이러한 설명대로 작성한 코드이다.

문제풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void add(vector<int>& copy, vector<int> nums) {
	if (nums.size() == 1)
		copy.push_back(nums[0]);
	else {
		vector<int> result;
		for (int i{ 0 }; i < copy.size(); i++) {
			if (i != 0) {
				if (copy[i - 1] + nums[i] < copy[i] + nums[i]) {
					result.pop_back();
					result.push_back(copy[i] + nums[i]);
				}
				result.push_back(copy[i] + nums[i + 1]);
			}
			else {
				result.push_back(copy[i] + nums[i]);
				result.push_back(copy[i] + nums[i + 1]);
			}
		}
		copy = result;
	}
}

int main() {
	int N, X;
	cin >> N;
	vector<int> results;
	for (int i{ 0 }; i < N; i++) {
		vector<int> fl;
		for (int a{ 0 }; a <= i; a++) {
			cin >> X;
			fl.push_back(X);
		}
		add(results, fl);
	}
	auto max = max_element(results.begin(), results.end());
	cout << *max;
}

void add

말했던 것과 같이 소거가 필요한 값들을 소거하며 계속 층마다 합을 저장해 내려갔다.

 

int main

마지막 층까지 내려간 후 남은 값들을 저장하는 배열에서 max_element를 통해 최댓값을 찾고 출력했다.

 

문제후기

규칙대로 하면 금방 풀리는 문제였다.