Dynamic Programming 5: DP 배열 설정의 중요성 (백준 14238, 17404, 12969번)

백준 14238번: 출근 기록

문제 설정은 간단하다. 

각 알파벳 A, B, C에 대해서 아래 조건을 금방 파악할 수 있다.

 

그렇지만 문제 조건을 잘 파악했다 하더라도 다음이 문제다.

기존 문제처럼 dp 배열이 1차원 또는 2차원이라고 가정하고 접근해보자.

 

DP 배열이 1차원이라면?

dp[n] = V : 길이가 n인 문자열 중 올바른 출근 기록인 경우의 수(또는 문자열들의 배열?)

점화식을 세울 때 dp[n]과 dp[n-1] 사이 관계를 어떻게 정의할 수 있는가?

길이가 n-1인 문자열 오른쪽 끝에 A를 추가했을 때, B를 추가했을 때 그리고 C를 추가했을 때 매번 기존 문자열의 끝에 어떤 문자가 오느냐에 따라 추가할 수 있는지 없는지가 달라진다.

 

또는 dp[n]에 길이가 n인 가능한 모든 문자열들을 배열로 저장한다고 해보자.

하지만 배열은 애초에 크기와 자료형이 일정한 값을 담기 위한 자료구조이기 때문에

어떤 배열에 크기(개수)가 각각 다른 배열을 저장하게 된다면 설사 코드가 돌아간다고 해도 결코 좋은 코드라고 할 수 없다.

 

즉 각 dp[n]에 담긴 문자열들의 배열 크기가 기하급수적으로 증가하는 건 물론, 결국 각 문자열에 대해 또 검사를 해야 하므로 코드가 매우 복잡해진다.

 

 

DP 배열이 2차원이라면?

앞서 각 문자열의 끝에 어떤 문자가 오느냐에 따라 추가할 문자 여부가 결정된다고 했다.

그럼 이렇게 생각해볼 수도 있겠다.

 

dp[n][c] = V : 길이가 n인 문자열 중 끝에 위치한 문자가 A(c = 0), B(c = 1) 또는 C(c = 2) 일 때 가능한 문자열의 개수 또는 문자열의 집합

 

그러나 2차원으로 설정해도 여전히 알파벳 C에 대해선 해결하지 못한다.

알파벳 C는 직전 문자뿐 아니라 2번째 이전 문자에도 의존하기 때문이다.

 

 

DP 배열을 3차원으로 만들자

그럼 직전 문자와, 2번째 전 문자 정보를 모두 담도록 설정하면 되지 않을까?

 

dp[n][c1][c2] = V : 길이가 n인 문자열 중 끝에 위치한 문자가 A(c2 = 0), B(c2 = 1) 또는 C(c2 = 2)이고 두번째 끝 문자가 A(c1 = 0), B(c1 = 1) 또는 C(c1 = 2)일 때 가능한 문자열의 개수 또는 문자열의 집합

 

거의 답에 근접했다. 하지만 이 역시도 답이 될 수 없다.

 

점화식을 세울 순 있다. 직전 문자와 2번째 전 문자의 정보가 dp 배열에 기록되어 있기 때문에 각 알파벳 A, B, C에 대해 별도의 if 문으로 쉽게 처리해줄 수 있다.

 

그러나 길이가 n인 문자열에 대해 끝 문자와 2번째 끝 문자가 각각 c1, c2인 문자열들이 여러 가지 있을 수 있기 때문에

이 각각의 경우를 추적해나가려면 여전히 문자열의 배열을 dp 배열에 저장해야 하며,

각 문자열에 대해 추적하는 방식은 매우 비효율적이다(직접 안해봐서 모르겠다. 근데 시도해보고 싶지는 않다)

 

 

핵심 정보가 무엇인가?

다시 한번 문제를 읽어보자. 문제 조건을 결정짓는 핵심 정보가 무엇인가?

문제에서는 어떤 알파벳의 조합을 입력으로 주고 그 알파벳들로 만든 순열 중 올바른 문자열이 하나라도 있다면 그 하나를 출력하라고 했다.

 

여기서 두 가지 중요한 포인트를 파악할 수 있다.

 

1. 중요한 건 문자열 그 자체(순서)가 아니라 문자열을 이루는 각 알파벳의 개수다.
2. 길이가 n이고, 각 알파벳 개수가 동일한 문자열이 여러 가지 있을 수 있다. 그러나 문제에선 가능한 경우 딱 한가지만 요구하므로 dp 배열에는 가능한 문자열을 찾으면 그대로 저장하고 업데이트하지 않는다.

 

그러나 문제에 대해 충분히 고민해본 사람이라면 2번째 사항에도 허점이 있다는 걸 눈치챘을 것이다.

길이가 9이고 각 알파벳 개수가 4,3,2인 문자열이 있다고 해보자.

 

 

같은 경우(길이가 9이고 각 알파벳 개수가 4,3,2)라 하더라도 끝에 오는 문자가 다를 수 있기 때문에 추가 가능한 문자도 달라지게 된다.

 

그럼 마지막으로 이렇게 시도해보자.

각 알파벳 A, B, C 개수(3차원)와 직전 문자, 2번째 전 문자(1+1차원)를 모두 dp 배열에 기록하는 것이다.

길이는 따로 저장할 필요가 없다. 어차피 각 알파벳 개수를 모두 합하면 길이와 동일하기 때문이다.

 

dp[a][b][c][p1][p2] = V : 알파벳 A의 개수가 a, B의 개수가 b, C의 개수가 c이며 끝 문자가 A(p1 = 0), B(p1 = 1) 또는 C(p1 = 2)이고 2번째 끝 문자가 A(p2 = 0), B(p2 = 1) 또는 C(p2 = 2)인 문자열

 

저렇게 설정하면 기존 2번째 사항의 문제점도 발생하지 않고 dp 배열에는 한 가지 값(문자열)만 담을 수 있다.

 

 

 

5차원 dp 배열을 이용한 풀이

import sys
input = sys.stdin.readline

records = input().rstrip('\n')
LENGTH = len(records)

numA = records.count('A')
numB = records.count('B')
numC = LENGTH - (numA+numB)

# dp = [a][b][c][p1][p2] : V -> 각 알파벳 개수가 a,b,c이고 
# 끝 문자가 p1(0~2), 2번째 끝 문자가 p2(0~2)인 문자열
dp = [ [ [ [
              ['']*3 
            for _ in range(3)] 
          for _ in range(numC+1)] 
        for _ in range(numB+1)] 
      for _ in range(numA+1)]
      

for i in range(3):
    if numA > 0:
        dp[1][0][0][0][i] = 'A'
    if numB > 0:
        dp[0][1][0][1][i] = 'B'
    if numC > 0:
        dp[0][0][1][2][i] = 'C'


for a in range(numA+1):
    for b in range(numB+1):
        for c in range(numC+1):
            if a > 0:
                # dp[a][b][c] <- A를 붙이는 경우
                for i in range(3):
                    for j in range(3):
                        if dp[a-1][b][c][i][j] != '':
                            dp[a][b][c][0][i] = dp[a-1][b][c][i][j] + 'A'
            if b > 0:
                # ....AB <- ...AA + B 또는 ...BA + B 또는 ...CA + B. 3가지 모두 가능
                # ....BB <- 땡!
                # ....CB <- ...AC + B 또는 ...BC + B 또는 ...CC + B 3가지 모두 가능
                # dp[a][b][c][B][A]
                for i in range(3):
                    for j in range(3):
                        # 바로 이전 문자가 B이면 B를 붙일 수 없지만(i != 1), B를 처음으로 쓰는 것이라면(b == 1) B를 붙이는 게 가능하다.
                        if b == 1 or i != 1:
                            if dp[a][b-1][c][i][j] != '':
                                # *...*X + B -> *...*
                                dp[a][b][c][1][i] = dp[a][b-1][c][i][j] + 'B'
                        
            if c > 0:
                # ....AC <- ...AA + C 또는 ...BA + C. ///// ...CA + C는 불가능.
                # ....BC <- ...AB + C. ///// ...BB + C 와 ...CB + C는 불가능.
                for i in range(3):
                    for j in range(3):
                        if c == 1 or (i != 2 and j != 2):
                            if dp[a][b][c-1][i][j] != '':
                                dp[a][b][c][2][i] = dp[a][b][c-1][i][j] + 'C'


def solution():
    for i in range(3):
        for j in range(3):
            if dp[numA][numB][numC][i][j] != '':
                return dp[numA][numB][numC][i][j]
    return -1
    
    
print(solution())

 

 

 

이 문제가 어렵게 느껴졌던 이유

기존 문제에선 1차원 또는 기껏해봐야 2차원 배열을 dp에 이용했었다.

여기선 무려 5차원 배열을 사용한다.

5차원 배열을 사용해본 경험도 없고, 쓰면 안된다는 편견이 강했기 때문에 문제 풀이 자체를 떠올리기 어려웠던 것 같다.

 

물론 배열의 차원을 늘릴수록 관리하기가 어렵고 코드가 복잡해지는 것도 사실이다.

그러나 문제 조건에 따라 필요하다면 과감하게 n >= 3 차원 이상의 dp 배열을 설정해서 풀 수 있어야 한다.