글 읽기 - DP식에 대한 질문드립니다!

strake32 6년 전 1

안녕하세요~

이 문제를 해결하신 다른 분의 DP식을 보게 되었는데 메모이제이션/재귀DP로 문제를 해결하셨더라고요.

그런데 몇 시간째 식을 봐도 이해가 잘 안되서 이렇게 글을 쓰게 되었습니다ㅠㅠ

if (st[alpha][0] == l && st[alpha][1] >= r){
   ms = -(l + r);
  }
  //ed:색상[0]~[1]의 끝나는위치->총 26개의 알파벳을 나타냄.
  if (ed[alpha][0] == l && ed[alpha][1]<r){
   ps = l + r;
  }

이 부분에서 l + r을 왜 저렇게 적용하는 건가요??

무지한 절 구원해주세요!

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int dp[5005][5005];
string s[2];
int st[26][2];
int ed[26][2];
int in[26][2];
int solve(int l, int r){
	int &ret = dp[l][r];
	if (ret != -1)
		return ret;
	if (l == s[0].length() && r == s[1].length()){
		return ret = 0;
	}
	ret = 1e9;
	int ms, ps;
	if (l<s[0].length()){
		//alpha는 현재 알파벳을 나타냄.
		int alpha = s[0][l] - 'A';
		ms = 0, ps = 0;
		//st:색상[0]~[1]의 시작위치->총26개의 알파벳을 나타냄.
		//현재 알파벳의 시작위치가 l과 같으며 이 알파벳은 아직 2번 째 라인에서 등장하지 않음.
		if (st[alpha][0] == l && st[alpha][1] >= r){
			ms = -(l + r);
		}
		//ed:색상[0]~[1]의 끝나는위치->총 26개의 알파벳을 나타냄.
		if (ed[alpha][0] == l && ed[alpha][1]<r){
			ps = l + r;
		}
		ret = min(ret, solve(l + 1, r) + ms + ps);
	}
	if (r<s[1].length()){
		int alpha = s[1][r] - 'A';
		ms = 0, ps = 0;
		if (st[alpha][0] >= l && st[alpha][1] == r){
			ms = -(l + r);
		}
		if (ed[alpha][0] <l && ed[alpha][1] == r){
			ps = l + r;
		}
		ret = min(ret, solve(l, r + 1) + ms + ps);
	}
	return ret;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
		while (T--){
		//엄청 큰수 초기화
		memset(st, 0x3f3f3f, sizeof(st));
		memset(ed, -1, sizeof(ed));
		memset(in, 0, sizeof(in));
		memset(dp, -1, sizeof(dp));
		cin >> s[0] >> s[1];
		for (int k = 0; k<2; k++){
			for (int i = 0; i<s[k].length(); i++){
				int alpha = s[k][i] - 'A';
				st[alpha][k] = min(st[alpha][k], i);
				ed[alpha][k] = max(ed[alpha][k], i);
				in[alpha][k] = 1;
			}
		}
		cout << solve(0, 0) << "\n";
	}

	return 0;
}

blou888 1년 전 0

님의 질문 덕에 솔루션을 떠 올렸습니다!!!

감사합니다!

if (st[alpha][0] == l && st[alpha][1] >= r){
ms = -(l + r);
}
//ed:색상[0]~[1]의 끝나는위치->총 26개의 알파벳을 나타냄.
if (ed[alpha][0] == l && ed[alpha][1]<r){
ps = l + r;
}

질문자 님 께서 올린 코드 부분의 해당 지점은

if (st[alpha][0] == l && st[alpha][1] >= r){
ms = -(l + r);
}

ms같은 경우는

l또는 r가 어찌됐건 특정 알파벳이 될겁니다.

그런데 그 알파벳이 l일때 시작점이고, r이라는 지점이 아직 끼어들지 않았을 때라는 if문입니다.

ms = -(l+r) => 즉 r개의 차가 끼어들었는데, 아직 2차선의 해당 색깔은 끼어들지 않았고, 1차선의 l개의 차선이 끼어들었을 때가 시작점이 되는 것입니다.

이 뜻만 보면 아직 감이 잘 안오실텐데

뒤의

ps에 담기는 값을 봅시다.

l이 증가하다가 마지막에 도달했습니다. 그런데 이미 중간에 r의 끝점은 이미 차선에 포함되어 있다는 뜻이죠

ps = r + l

(즉 오른쪽은 r개의 차가 이미 끼어들었고, l번째에 해당 색깔이 있다는 뜻입니다.)

그래서 재귀를 짤 때, solve + ps + ms 가 성립합니다.

preview

그림판으로 그려서 조잡하지만, l대와 r대가 추가되었을 때 중복되는 l,r 구간이 존재 합니다. 이를 빼주기 위해서입니다.

댓글을 작성하려면 로그인해야 합니다.