백준 27212 미팅 - 파이썬

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

27212번: 미팅

악수 얘기만 들었을 때는 전깃줄 문제가 떠올랐는데 갑자기 만족도를 구하라고 한다.
DP로 접근해서 해결했다.




dp[a][b]는 A대학 a번 학생이 B대학에서 b번 이하의 학생과 악수를 할 수 있을 때 얻을 수 있는 총만족도의 최댓값으로 정했다.

말이 이상한데, 예를 들어 문제의 예제를 살짝 변형해서 아래와 같은 조건이 있다고 치자.

W = | 10   1 |
    |  1  10 |
    
A = [1, 2]
B = [1, 2, 2]

dp[1][1]은 A학교 1번 학생이 B학교 1번 이하의 학생과 악수를 할 수 있을 때 얻을 수 있는 만족도의 최댓값이다.
악수를 안 하면 만족도는 0, B학교 1번 학생과 악수를 한다면 만족도는 10이 될 것이다.
따라서 dp[1][1] = 10이다.


dp[1][2]는 A학교 1번 학생이 B학교 2번 이하의 학생과 악수를 할 때 얻을 수 있는 만족도의 최댓값이다.
B학교 2번과 악수를 한다면 만족도는 1이 돼버리니 그냥 1번 학생과 악수하는 편이 낫다.
따라서 dp[1][2] 역시 10이다. dp[1][3]도 마찬가지로 10이다.



A학교 1번 학생이 악수를 마쳤으니 2번 학생으로 넘어간다.

악수하면서 팔이 겹치면 안 되니 dp[2]는 dp[1]에 비해 추가적인 조건들을 고려해주어야 한다.
dp[2][1]을 구할 때 고려해 줄 경우의 수는 두 가지 정도이다.

1) A학교 1번이 B학교 1번과 악수, A학교 2번은 악수 안 함 > 10
2) A학교 1번은 악수 안 함, A학교 2번은 B학교 1번과 악수 > 1

따라서 dp[2][1]은 10이다.




dp[2][2]부터는 세 경우 중 하나이다.

1) A학교 2번이 B학교 2번과 악수함
> dp[2][2] = (A학교 1번은 B학교 1번 이하와 악수한 최댓값) + (지금 악수의 만족도) == dp[1][1] + 10 == 20
2) A학교 2번이 B학교 1번 이하와 악수함
> dp[2][2] = dp[2][1] == 1
3) A학교 2번은 악수 안 함
> dp[2][2] = A학교 1번이 B학교 2번 이하의 학생과 악수한 최댓값 == dp[1][2] == 10

따라서 dp[2][2]는 20이다.
이런 방식으로 쭉 경우의 수를 고려해서 dp를 채워가면 된다.






설명이 두서없고 긴데...
정리해서 규칙을 찾아보자면, dp[a][b]는 크게 세 가지 경우 중 하나에 해당할 것이다.

1) a번 학생이 b번 학생과 악수를 함
> dp[a][b] = dp[a-1][b-1] + (a와 b가 악수할 때의 만족도)
2) a번 학생이 b번 미만의 학생과 악수를 함
> dp[a][b-1]
3) a번 학생은 악수를 아예 안 함
> dp[a-1][b]

dp[a][b]에 1) ~ 3) 중 최댓값을 저장해 주는 방식으로 풀었다.
그렇다면 dp[N][M]이 모든 경우의 수를 고려했을 때 얻을 수 있는 만족도의 최댓값, 즉 정답이다.

N, M, C = map(int, input().split())
W = [list(map(int, input().split())) for _ in range(C)]

A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

dp = [[0] * (M+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, M+1):
        dp[i][j] = max(max(dp[i-1][j-1] + W[A[i]-1][B[j]-1], dp[i][j-1]), dp[i-1][j])

print(dp[N][M])