Connected Profile DP - 싼 비용 (BOJ 1144)

Difficulty: Diamond III

 

Connected Profile을 배우기 전 BOJ 1648 (격자판 채우기, Platinum III)를 먼저 보고 오시는 것을 추천드립니다. 해당 문제에서의 DP 아이디어 중 가장 많이 쓰이는 것이 비트필드를 이용하여 최근 M칸의 state를 DP 요소로 잡는 것인데, 이 문제 역시 이와 비슷한 양상을 띄고 있습니다.

이 문제 역시 최근 M칸의 state를 저장하는 것이 핵심입니다. 여기서는 이들의 연결 관계 또한 트래킹하는 것이 중요합니다. 연결된 Profile이 여러 개 있으면, 이를 M개 칸에 나타나는 순서대로 1, 2, 3...이라 합니다. 

 

N, M은 한 자리 자연수이므로 State는 한 자리 수로 나타낼 수 있습니다. 즉, M칸의 state를 길이 M의 string 하나로 나타낼 수 있다는 뜻입니다. 이 때, 이전의 칸이 M개 이하라면 그 전의 수는 모두 '0'으로 처리합니다.

그러면 우리는 board[i][j][state]를 (state에서 (i,j)부터 채워나가며 조건을 만족시키고 만들 수 있는, (i,j)부터 마지막 칸까지 수의 합의 최솟값)으로 잡을 수 있습니다.

즉, 우리가 최종적으로 구하는 값은 board[0][0]["00...0" (0 M개)]가 됩니다.

예시

String으로 저장되기 때문에, unordered_map을 통해서 dp 값을 저장할 수 있습니다. 최소값을 구하는 함수이므로, find가 안 된다면 default 값이 INF임에 유의합시다.

이제 DP 전이를 본격적으로 시작하기에 앞서 구현해야 할 함수가 몇 개 있습니다.

 

1) 정규화

1, 2, 3...은 M개 중에서 나타내는 순서대로 적혀있기에 임의의 string을 정규화하는 과정이 필요합니다. 이 정규화 과정까지 거치고 나면 state로 가능한 경우의 수는 그렇게 많은 편이 아닙니다. 그래서 작은 M, N에 대해서는 은근 빨리 코드가 돌려지게 됩니다.

 

2) 합치기

일단 state인 상태에서 cell을 선택하지 않으면 ('0'), 이 경우는 state[1:] + '0'을 정규화한 것임을 알 수 있습니다. 그런데 만약 cell을 선택한다면 어떻게 될까요? 일단 정규화는 나중에 해도 되기 때문에 '9'라는 임시 글자로 둡니다. 그러면 바로 위의 칸이 이미 선택됐다면, 즉 state[0]이 '0'이 아닐 시, state[0] 역시 '9'로 변해야 하고, state[0]와 같은 수를 가진 글자 모두 '9'로 바뀌어야 합니다. 이는 바로 왼쪽의 칸에 대해서 역시 적용되는데, 이 때 만약 선택하는 칸이 1열에 있다면 '바로 왼쪽의 칸'이 없다는 점에 유의하면서 구현해야 합니다. 그 다음에 이를 정규화하면 합친 state가 나오게 됩니다.

 

3) 건너뛰기의 가능성 판정

이제 건너뛰면 Profile이 끊겨서 다시는 연결시킬 방법이 없을 수도 있습니다. 이 때는 cell을 선택하지 않으면 안 됩니다. i번째 칸이 정해지면 i-M번째 칸은 다시 연결될 수 있는 방법이 없기에, 만약 state[0]가 '0'이 아니고 (즉, '1'이고), state[1:] 중 state[0]와 같은 글자가 하나도 없으면 건너뛸 수 없음을 반환해야 합니다. 여기서 주의할 점은 "1000..00" 역시 False를 반환해야 합니다. 이 때는, 'Profile이 일찍이 끝나는 경우가 가능해서 Skip 가능하다고 예외 케이스를 만들어줘야 하지 않나?'라 생각할 수 있습니다. 그러나, 실제로 여기서 True를 반환하면, state는 지난 M칸의 상태만을 저장하기 때문에 아래와 같은 답안이 반환될 수 있습니다. Profile이 일찍 끝나는 경우가 최소인 케이스에 대해서는 DP 전이 과정에서 다뤄야 합니다.

state의 memory는 제한되어 있으므로 잘못된 skip 구현으로 인해 이런 예외가 나올 수 있다.

그러면 이제 DP 전이를 해보도록 합시다.

함수 check(int a, int b, string u)는 dp[a][b][u]를 구하는 과정을 재귀적으로 나타낸 것입니다.

만약 a == n이면, 보드의 끝에 다다랐다는 뜻인데, 이 때, u를 검사한다.

1) u가 '0'과 '1'로만 이루어져있다 - Valid profile이다 - 반환값 0

2) u가 '2' - '9' 중 하나가 들어간다 - 보드의 끝까지 갔으나, profile이 나뉘어져있다 - 즉 이 경우는 고려하면 안 되므로 최솟값이 될 리가 없게 INF를 반환한다.

 

이제 이를 제외한, 다음 칸 check를 호출하는 방법을 봅시다. 

일단 u가 '0'과 '1'로만 이루어져 있을 시, 여기서 더 이상 원소를 택하지 않는 방법이 있으므로 board[a][b][u]를 INF 대신 0으로 초기화합니다. 이러면 위에 언급한 "1000..00"에 대해서도 고려를 한 것입니다.

그 뒤에는, 합친 경우를 보면서 다음 칸에 대한 check를 호출합니다. 이 때, 칸을 선택했으므로, [a][b]에 있는 숫자를 dp에 더하는 걸 잊지 않도록 합시다.

그리고, skip이 가능한 경우에는, skip한 경우를 보면서 다음 칸에 대한 check를 호출합니다.

그러면 board[0][0]["00...0" (0 M개)]를 출력할 시 답이 나오게 됩니다.

이를 모두 구현하면 AC를 받을 수 있습니다.

 

Source Code - http://boj.kr/d0fe61ba41e242b6ac3ded7ff0ede965