[프로그래머스] 정수 삼각형

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

​

제한사항

삼각형의 높이는 1 이상 500 이하입니다.

삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

 

완전 탐색으로 첫 시도(C++)

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

int answer = 0;

void down(int CurrentSum, int CurrentHeight, int CurrentPosition, int Height, vector<vector<int>> triangle) {
	if (CurrentHeight == Height) {
		if (CurrentSum >= answer)
			answer = CurrentSum;
		else
			;
	}
	else {
		CurrentSum = CurrentSum + triangle[CurrentHeight][CurrentPosition];
		CurrentHeight++;
		down(CurrentSum, CurrentHeight, CurrentPosition, Height, triangle);
		down(CurrentSum, CurrentHeight, CurrentPosition + 1, Height, triangle);
	}
}

int solution(vector<vector<int>> triangle) {
	answer = triangle[0][0];
	down(triangle[0][0],1,0, triangle.size(), triangle);
	down(triangle[0][0],1, 1, triangle.size(), triangle);
	cout << answer;
	return answer;
}

 

효율성에서 완전 실패했다. 문제에서 말한대로 동적 계획법에 맞춰서 풀어야 답이 나올 것 같다.

​

​

동적 계획법

주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

​

​

삼각형의 양 끝 사이드를 제외한 나머지는 알고리즘 라이브러리의 max함수를 사용하여 값을 비교해가면서 더해 내려가게 다시 구현하였다.

자신을 기준으로

자신의 값 = 위의 왼쪽과 오른쪽 중 더 큰값 + 자신과의 값

이렇게 계속 값을 업데이트 후 저장하면서 끝까지 내려간다.

​

양 끝 사이드는 그냥 벽 타고 내려가면 된다

​

​

동적 계획법으로 다시 시도(C++)

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

int solution(vector<vector<int>> triangle) {
	int answer = 0;
	int size = triangle.size();
	vector<vector<int>> temp(size, vector<int>(size)); //더한 값 저장할 벡터

	temp[0][0] = triangle[0][0];
	for (int i = 1; i < size; i++) {
		for (int j = 0; j <= i; j++) { 
			if (j == 0) //왼쪽 사이드
				temp[i][0] = temp[i - 1][0] + triangle[i][0];
			else if (j == i) //오른쪽 사이드
				temp[i][j] = temp[i - 1][j - 1] + triangle[i][j];
			else { //그 외
				temp[i][j] = max(temp[i - 1][j - 1] + triangle[i][j], temp[i - 1][j] + triangle[i][j]);
			}

			if (i == size - 1) //마지막 레벨
				answer = max(temp[i][j], answer);
		}
	}
	return answer;
}

 

몇 번 오류 거친 뒤에 성공!

​

좀 더 머리를 굴리면서 문제를 풀어야겠다.

​

​

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형 | 프로그래머스