백준 11055, 1149

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

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

11055번: 가장 큰 증가 부분 수열

풀이방법

일반적인 top down 메모제이션 풀이로 풀면 됨.

전체코드

#include <iostream>
#include <algorithm>

using namespace std;
int A[1001];
int dp[1001];
int N;

void dpInit()
{
	for (int i = 0; i <= N; i++)
		dp[i] = -1;
}

void Input()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> A[i];
}

int getMaxSum(int pos)
{
	int& ret = dp[pos];
	if (ret != -1) return ret;

	ret = A[pos];
	for (int next = pos + 1; next <= N; next++)
		if (A[pos] < A[next])
			ret = max(ret, getMaxSum(next) + A[pos]);
	
	return ret;
}

int main()
{
	Input();
	dpInit();
	cout << getMaxSum(0);
	return 0;
}

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

1149번: RGB거리

풀이방법

조건중 i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
이 부분만 유의하면 그냥 탑다운 풀이임.

전체코드

#include <iostream>
#include <algorithm>

#define INF 987654321

using namespace std;
int colors[3][1001];
int dp[3][1001];
int N;

void dpInit()
{
	for (int i = 0; i < 3; i++)
		for (int j = 0; j <= N; j++)
			dp[i][j] = -1;
}

void Input()
{
	cin >> N;
	for (int pos = 1; pos <= N; pos++)
		for (int color = 0; color < 3; color++)
			cin >> colors[color][pos];
}

int getMinValue(int color, int pos)
{
	int& ret = dp[color][pos];
	if (ret != -1) return ret;

	//기저사례 ㅎㅎ
	if (pos == N)
		return ret = colors[color][pos];

	ret = INF;
	for (int nColor = 0; nColor < 3; nColor++)
	{
		//색이 같으면 안된다.
		if (nColor == color && pos!=0)
			continue;
		ret = min(ret, getMinValue(nColor, pos + 1)+ colors[color][pos]);
	}
	return ret;
}

int main()
{
	Input();
	dpInit();
	cout << getMinValue(0, 0);
	return 0;
}

후기