[BOJ] 27212 미팅

미팅 27212

2023-1 쇼미더코드에 나온 3번 문제이다.
난이도 골드 3 미팅
https://www.acmicpc.net/problem/27212

풀이

해당 문제의 풀이는 dp이다. (dfs로 풀면 시간 초과가 난다.)
정확하게 얘기하자면 LCS, edit distance 문제와 비슷한 유형으로 예를 들어 A원소 1000개, B원소 1000개가 있으면 그냥 2개, 3개 있다고 생각하고 문제를 풀자는 방법이다.

즉, 적은 수의 원소의 경우부터 천천히 구하고 하나씩 원소의 수를 늘려 답을 구하자는 풀이이다. dp[1][2] -> dp[999][999]

이 미팅 문제의 경우, dp[i][j]에서 총 3가지의 경우로 나뉠 수 있다.
i) A대학의 i번째가 B대학의 j번째와 매칭이 된다.
iii) A대학의 i가 매칭이 안 된다. (A[i]가 사용 안 됨)
ii) B대학의 j가 매칭이 안 된다. (B[j]가 사용 안 됨)

그렇다면 결국 수식으로는 이렇게 표현할 수 있다.
i) dp[i][j] = dp[i-1][j-1]+w[i][j]
ii) dp[i][j] = dp[i-1][j]
iii) dp[i][j] = dp[i][j-1]

우리는 매칭 점수가 가장 높은 경우를 dp에 저장할 것이니 결국 수식은 이렇게 된다.
dp[i][j]
= Max(i,ii,iii)
= Max(dp[i-1][j-1]+w[i][j], dp[i-1][j], dp[i][j-1]);

Reference

https://www.youtube.com/watch?v=wh7KS2gXNHc (34:00~)