알고스팟 _ 삼각형 위의 최대 경로

2020-05-08 · 배운 것 · 4분 읽기

https://algospot.com/judge/problem/read/TRIANGLEPATH

접근

시간 : 5초, 테스트케이스 : 최대 50개, n : 최대 100

딱봐도 이 문제는 완전탐색으로 풀기에는 중복되는 연산이 많다. 저번 포스팅들에서 이것과 흡사한 문제들이 왜 시간이 안되는지 여러번 설명했기 때문에 왜 시간초과인지는 생략하도록 하겠다. 이 문제도 전형적인 동적계획법 문제처럼 중복되는 계산이 많다. 이 중복되는 연산을 줄이기 위해서 메모라이즈 기법을 사용하자!

풀이방법

위에서 설명했던것처럼 중복되는 연산을 막기위해서 메모라이즈 방식이 사용하겠다.
cache[][]배열 ( -1 : 아직 계산안함, 그외 : 계산된 값 ) 을 만들고 이를 이용해서 아래와 아래 오른쪽중에 큰값을 받자.

//바로 아래숫자, 오른쪽 아래 숫자 체크
for (int i = 0; i < 2; i++)
	ret = max(ret, getMaxSum(h + 1, w + i));
	
ret += triangle[h][w];

혹시 설명이 너무짧아 이해가 안간다면 비슷한 유형의 문제를 리뷰해놓았으니 보면 좋을것같다.
https://blog.fxjodo.com/blog/110/

백준 2098번 _ 외판원 순회

전체코드

#include <iostream>
#include <algorithm>

using namespace std;
int triangle[101][101];
int cache[101][101];
int n;

void cacheInit()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			cache[i][j] = -1;
}

void Input()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			cin >> triangle[i][j];
}

int getMaxSum(int h, int w)
{
	int& ret = cache[h][w];
	if (ret != -1) return ret;

	//다내려왔을때
	if (h == n)
		return triangle[h][w];

	//바로 아래숫자, 오른쪽 아래 숫자 체크
	for (int i = 0; i < 2; i++)
		ret = max(ret, getMaxSum(h + 1, w + i));
	
	ret += triangle[h][w];

	return ret;
}

int main()
{
	int testcase;
	cin >> testcase;
	for (int i = 0; i < testcase; i++)
	{
		Input();
		cacheInit();
		cout << getMaxSum(1, 1) << '\n';
	}
	return 0;
}

후기

침대에 누워 종만북을 보다가 이건 간단히 풀고 잘수있을것 같아 컴퓨터를 켜서 풀고 리뷰까지 해보았다. 금방 풀려서 다행이다.

이제 자야지 히히