[ boj : 14677 ] 병약한 윤호

www.acmicpc.net/problem/14677

14677번: 병약한 윤호

문제 : 윤호는 알약을 먹습니다. B->L->D 순으로 먹습니다. 이때 최대로 먹을 수 있는 알약의 개수를 구하시오

 

해설 : 이 문제도 지난 포스팅한 문제와 크게 다를 바 없는 문제입니다.

왼쪽에서 선택하던 오른쪽에서 선택하던 어떤 선택을 하던지 간에 정답의 후보군이 될 수 있는 케이스들의 상태가 변하게 되고 우린 이를 BFS로 탐색해서 답을 찾을 수 있겠죠.

 

그럼 왼쪽,오른쪽 둘 중 어느쪽을 선택하면 상태값이 변하게 되니 이를 기준으로 '상태배열'을 생성하여 BFS를 탐색해주면 답을 도출할 수 있습니다.

 

#include<bits/stdc++.h>

using namespace std;

struct info {
	int a, l, r;
};

int n, arr[1510],visit[1510][1510];
string s;

int bfs(int l, int r);

int main()
{
	cin >> n >> s;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == 'B')arr[i] = 0;
		else if (s[i] == 'L')arr[i] = 1;
		else arr[i] = 2;
	}
	cout << bfs(0, 3 * n - 1);
	return 0;
}
int bfs(int l, int r)
{
	int ret = 0;
	queue<info> q;
	visit[l][r] = 1;
	if (arr[l] == 0) {
		q.push({ 0,l + 1,r });
		visit[l+1][r] = 1;
	}
	if (arr[r] == 0) {
		q.push({ 0,l,r - 1 });
		visit[l][r - 1] = 1;
	}
	while (!q.empty())
	{
		int size = q.size();
		for (int s = 0; s < size; s++) {
			info cur = q.front();
			q.pop();

			if (cur.l > cur.r)continue;
			if (arr[cur.l] == (cur.a + 1) % 3 && !visit[cur.l+1][cur.r]) {
				q.push({ (cur.a + 1) % 3,cur.l + 1,cur.r });
				visit[cur.l + 1][cur.r] = 1;
			}
			if (arr[cur.r] == (cur.a + 1) % 3 && !visit[cur.l][cur.r - 1]) {
				q.push({ (cur.a + 1) % 3,cur.l,cur.r - 1 });
				visit[cur.l][cur.r - 1] = 1;
			}
		}
		ret++;
	}
	return ret;
}

 

두번째 방법은 다이나믹 프로그래밍을 이용하는 것 입니다.

결국 BFS로 탐색을 한 코드를 짜고 보니 어떤 선택을 하고 상태값이 변하고, 이를 상태배열로 중복된 값들을 걸러주었으니 메모이제이션 기법을 사용해서 왼쪽 선택했을 경우 , 오른쪽 선택했을 경우 중 최대값을 저장해두고 return 시켜 주면 되겠습니다.

 

#include <bits/stdc++.h>
using namespace std;

int n;
string s;

int dp[1510][1510];
int f(int x,int y,char prev);

int main() {
	cin>>n>>s;
	memset(dp,-1,sizeof(dp));
	cout<<f(0,3*n-1,' ');
	return 0;
}
int f(int l,int r,char prev)
{
	if(l>r)return 0;
	int &ret = dp[l][r];
	if(ret!=-1)return ret;
	
	ret=0;
	if(s[l]=='B' && prev==' ' || s[l]=='B' && prev=='D' || s[l]=='L' && prev=='B' || s[l]=='D' && prev=='L')
		ret = max(ret,f(l+1,r,s[l])+1);
	if(s[r]=='B' && prev==' ' || s[r]=='B' && prev=='D' || s[r]=='L' && prev=='B' || s[r]=='D' && prev=='L')
		ret = max(ret,f(l,r-1,s[r])+1);
	return ret;
}