BOJ) 1932 정수 삼각형 <C++>

문제

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

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

 

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

 

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

 

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

 

로직

이번 문제는 입력을 어떤 방식으로 저장하느냐가 가장 큰 고민거리였다. 일단은 2차원 벡터를 활용해야 겠다고 생각했다. 저장하는 방식은 아래의 그림처럼 생각하였다.

• 삼각형의 크기는 1씩 늘어난다

따라서 arr[n]의 각 벡터를 들어갈 수 있는 사이즈 만큼 공간 할당을 미리 해 주었다. 

 

이제 입력에 대한 고민을 마쳤으니 이 값들을 가지고 어떻게 각 구간에서의 합들을 저장할지 고민해 보았다.

개념은 어렵지 않았다. 이전 층에 있는 값들 중 가져올 수 있는 값(좌 or 우)사이의 최대 값을 가져오면 되는 것이다.

 

아래의 그림을 살펴보자

위와 같은 경우 1은 가져올 수 있는 값, 즉 3과 8 중 큰 값을 가져와서 더하면 된다. 

왼쪽의 8은 가져올 수 있는 값이 3밖에 없기 때문에 그대로 3을 더하면 된다.

오른쪽도 마찬가지로 그냥 8을 더하면 된다. 

 

이 경우를 의사 코드로 작성해보니 아래와 같이 나왔다.

 

분기를 너무 많이 넣어줘야 하다보니 코드가 마음에 들지 않았다. 그래서 새로운 방법을 생각해 보게 되었다.

 

만약 젤 앞의 값과 젤 뒤의 값도 비교할 값이 있으면 어떨까??

그래서 이 빈 공간들을 0으로 채워보았다.

이렇게 만들고 나니 8도 왼 or 오 중 큰값을 골라서 더할 수 있게 되었다. 

어차피 삼각형 내부의 값은 양수이고 각 끝이 0으로 채워져 있다면 무조건 삼각형 내부의 값을 선택하게 될 것이다.

 

그래서 입력을 세로 2칸, 가로 2칸을 더 받아서 만들어주었다.

 

카테고리

• DP

 

코드

 

 

#include <iostream>
#include <vector>

std::vector<std::vector<int> > dp_vector;
int n;
int result;

void output()
{
	for (int i = 1 ; i <= n ; i++)
		result = std::max(result, dp_vector[n + 1][i]);
	std::cout << result;
}

void solution()
{
	for (int i = 2 ; i < n + 2; i++)
		for (int j = 0 ; j < i; j++)
			dp_vector[i][j] += std::max(dp_vector[i - 1][j], dp_vector[i - 1][j - 1]);
}

void input()
{
	std::cin >> n;
	dp_vector.resize(n + 2);
	for (int i = 0 ; i < n + 2; i++)
		dp_vector[i].resize(i + 1);
	for (int i = 2 ; i < n + 2 ; i++)
		for (int j = 1 ; j < i; j++)
			std::cin >> dp_vector[i][j];
}

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

int main()
{
	preset();
	input();
	solution();
	output();
}