백준-설탕 배달

백준-설탕배달(2839)

메모이제이션(memoization)을 사용해 백준 2839번 문제를 풀어보았다.

재귀호출을 사용한 전수조사

int solve(int m, int res)
{
	if (m < 0) return -1;
	if (m == 0) return res;
	int a = solve(m - 5, res+1);
	int b = solve(m - 3, res+1);
	if (a != -1 && b != -1) return a < b ? a : b;
	else if (a == -1 && b != -1) return b;
	else if (a != -1 && b == -1) return a;
	else return -1;
}

위의 방법처럼 했더니 당연하게도 시간초과가 났다.
N의 최대 크기가 5000이었는데, 재귀호출을 하면 최적의 해를 찾는 이진 탐색 트리의 최소 깊이만 해도 1000이다.

그래서 위 코드에 메모이제이션을 넣어 사용해보았다.

int solve(int m, unordered_map<int,int>& memo)
{
	if (m < 0) return -1;
	if (m == 0) return 0;

	int a, b;
	if (memo.find(m - 5) != memo.end()) a = memo[m - 5];
	else {
		a = solve(m - 5,  memo);
		memo.insert(make_pair(m - 5, a));
	}
	if (memo.find(m - 3) != memo.end()) b = memo[m - 3];
	else {
		b = solve(m - 3, memo);
		memo.insert(make_pair(m - 3, b));
	}

	if (a != -1 && b != -1) return a < b ? a+1 : b+1;
	else if (a == -1 && b != -1) return b+1;
	else if (a != -1 && b == -1) return a+1;
	else return -1;
}

Hash map을 사용해 계산한 값들을 저장해준다.
만약 hash map의 key가 존재하면, 해당 계산을 수행한 적이 있는 것이다.
key가 존재한다면 key에 해당하는 value를 가져오기만 하면 된다.
따라서 이미 했던 재귀호출들을 또 하는 비효율을 없앨 수 있다.

결과는 성공이다.

공부를 위해 기록해놓은 것입니다. 틀린 것이 있다면 지적해주시면 감사드리겠습니다!