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

strake32 2년 전 0

안녕하세요~

이 문제를 해결하신 다른 분의 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;
}

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

문제

문제

출처

ACM-ICPC

DP식에 대한 질문드립니다!

strake32 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말