백준 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 배열에 저장해야 하며,
각 문자열에 대해 추적하는 방식은 매우 비효율적이다(직접 안해봐서 모르겠다. 근데 시도해보고 싶지는 않다)
핵심 정보가 무엇인가?
다시 한번 문제를 읽어보자. 문제 조건을 결정짓는 핵심 정보가 무엇인가?
문제에서는 어떤 알파벳의 조합을 입력으로 주고 그 알파벳들로 만든 순열 중 올바른 문자열이 하나라도 있다면 그 하나를 출력하라고 했다.
여기서 두 가지 중요한 포인트를 파악할 수 있다.
- 중요한 건 문자열 그 자체(순서)가 아니라 문자열을 이루는 각 알파벳의 개수다.
- 길이가 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 배열을 설정해서 풀 수 있어야 한다.
백준 17404번: RGB 거리 2
앞서 본 14238번(출근 기록)과 결이 비슷한 문제다.
14238번에선 현재 문자에 대해 왼쪽 그리고 2번째 왼쪽 문자를 고려해야 했다면
이 문제에선 왼쪽 문자와 오른쪽 문자를 고려해주면 된다.
그리고 각 문자(빨강, 초록, 파랑) 구분 없이 이웃하는 문자가 다르기만 하면 되므로 14238번보다는 좀 더 단순한 설정이라고 할 수 있다.
dp 배열은 이렇게 정의 내릴 수 있다.
dp[n][c1][c2] = n-1번째 집을 c1(c1 = 0이면 red, c2 = 1이면 blue, c2=2이면 green)으로 칠했을 때 n번째 집을 c2로 칠하는 비용을 더한 값
이렇게 dp 배열을 설정하고 코드를 짜보자.
for i in range(3):
# dp[0]에 대해서는 왼쪽 칸이 없다고 가정
dp[0][i][0] = costs[0].red
dp[0][i][1] = costs[0].green
dp[0][i][2] = costs[0].blue
for i in range(1, N-1):
for c_prev in range(3):
for c_cur in range(3):
for j in range(3):
if dp[i-1][j][c_prev] > 0 and c_prev != c_cur:
dp[i][c_prev][c_cur] = dp[i-1][j][c_prev] + costs[i][c_cur]
하지만 이 문제가 14238번 문제와 결정적으로 다른 점이 하나 있다.
1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
첫 문자(1번 집)는 마지막 문자(N번 집)와 달라야 한다.
위 코드에서 dp[N-1]을 최종적으로 업데이트하는 과정을 살펴보자.
N-1번째 집은 0번째 집과 색깔이 달라야 하기 때문에 dp[0]과 비교를 해서 값을 구해야 한다.
근데 dp[N-1]은 dp[N-2]에도 의존하고, dp[N-2]의 최소 비용은 차례로 dp[N-3]에, dp[N-3]은 dp[N-4]... 해서 dp[0]에도 의존하게 된다.
결국 dp[N-1]번째를 구하기 위해서는 꼬리에 꼬리를 물듯이 dp[0]의 색깔 상태를 추적할 수밖에 없고
이는 '현재 상태(큰 문제)가 이전 상태(작은 문제)의 값에만 의존한다'는 dynamic programming의 주요 개념에 위배된다.
초기 조건을 결정한 후 비교하기
위에서 문제가 발생했던 이유는 결국 첫번째(또는 마지막)집의 색깔이 결정되지 않았기 때문이다.
그렇다면 아예 첫번째 집의 색깔이 결정되었다고 가정하고 풀면 어떨까?
어차피 첫번째 집 색깔은 빨강, 초록 또는 파랑 3가지밖에 되지 않으므로
결과를 3번만 도출해서 각 결과값을 비교하면 수월할 것 같다.
만약 0번째 집의 색깔이 정해진다면 1번째 집은 바로 왼쪽, 즉 0번째 집의 색깔만 고려하면 되고
2번째 집은 1번째 집의 색,
3번째 집은 2번째 집의 색...
이런 식으로 바로 왼쪽 집의 색깔만 고려하면 되기 때문에 dp 배열을 한 차원 줄일 수 있다(기존에는 왼쪽, 오른쪽 집의 색깔을 모두 고려해서 3차원)는 장점도 있다.
아래는 풀이 코드다.
import sys
input = sys.stdin.readline
N = int(input())
costs = [list(map(int, input().split())) for _ in range(N)]
def simulate(init_col):
dp = [[float('inf')]*3 for _ in range(N)]
dp[0][init_col] = costs[0][init_col]
for i in range(1, N):
for c_cur in range(3):
for c_prev in range(3):
if c_prev != c_cur and dp[i-1][c_prev] != float('inf'):
dp[i][c_cur] = min(dp[i][c_cur], dp[i-1][c_prev])
if dp[i][c_cur] != float('inf'):
dp[i][c_cur] += costs[i][c_cur]
if init_col == 0:
min_cost = min(dp[-1][1], dp[-1][2])
elif init_col == 1:
min_cost = min(dp[-1][0], dp[-1][2])
else:
min_cost = min(dp[-1][0], dp[-1][1])
return min_cost
answer = float('inf')
for color in range(3):
answer = min(answer, simulate(color))
print(answer)
백준 12969번: ABC
문제 설명이 아주 간결하다. 제약 조건도 많지 않다.
문제 설명이 짧다면 둘 중에 하나다. 아주 쉽거나, 어렵거나.
이 문제는 어려운 편에 속한다(골드 1).
워낙 문제 설명이 함축적이기 때문에 직접 손으로 써보면서 패턴을 파악하는 게 우선이다.
손으로 직접 써보면 기존 문자열의 오른쪽 끝에 추가하는 문자 A, B, C에 따라 더해지는 쌍의 개수가 달라지며,
더해지는 쌍의 개수는 이전 문자열의 상태(A, B, C 각 개수)에 의존함을 알 수 있다.
DP는 '현재 상태(큰 문제)가 이전 상태(작은 문제)에만 의존하며, 이전 상태는 과정을 반복해도 값이 변하지 않는다'는 전제를 기초로 하고 있음을 명심하자.
DP 배열의 설정
문제 조건을 올바르게 파악했다면 DP 배열의 차원, 그리고 각 차원이 의미하는 값을 정의내리는 것도 간단하다.
핵심 정보는 2가지다.
- 이전 문자열에서 알파벳 A, B, C의 개수 -> 3차원
- 이전 문자열에서 0 ≤ i < j < N 이면서 S[i] < S[j]를 만족하는 (i, j) 쌍의 개수 -> 1차원
따라서 dp 배열은 총 4차원이며,
이렇게 정의내릴 수 있다.
dp[a][b][c][K] = S : 알파벳 A의 개수가 a, B의 개수가 b, C의 개수가 c이며 쌍의 개수가 K개인 문자열
14238번(출근 기록)과 동일하게 어떤 제약 조건이 주어졌을 때,
가능한 문자열이 여러 가지이며 우리는 그 중 하나만 출력하면 된다.
따라서 dp 배열은 가능한 문자열 하나만을 저장하되,
가능한 문자열들 중 어떤 문자열을 택하든 dp 배열의 다음 상태에 영향을 주지 않도록 하면 된다.
풀이
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
dp = [ [ [ ['']*(K+1)
for _ in range(N+1)]
for _ in range(N+1)]
for _ in range(N+1)]
dp[1][0][0][0] = 'A'
dp[0][1][0][0] = 'B'
dp[0][0][1][0] = 'C'
for a in range(N+1):
for b in range(N+1):
for c in range(N+1):
if a + b + c > N:
break
if a > 0:
for p in range(K+1):
# A를 붙인 경우
if dp[a-1][b][c][p] != '':
dp[a][b][c][p] = dp[a-1][b][c][p] + 'A'
if b > 0:
for p in range(K+1):
if dp[a][b-1][c][p] != '':
if p+a <= K:
dp[a][b][c][p+a] = dp[a][b-1][c][p] + 'B'
if c > 0:
for p in range(K+1):
if dp[a][b][c-1][p] != '':
if p+a+b <= K:
dp[a][b][c][p+a+b] = dp[a][b][c-1][p] + 'C'
def solution():
for a in range(N+1):
for b in range(N+1):
c = N - (a+b)
if c >= 0 and dp[a][b][c][K] != '':
return dp[a][b][c][K]
return -1
print(solution())
풀고 나니 쉽게 느껴지는 게 당연하지만 짧은 문제 설명에서 패턴을 파악하고 점화식을 찾기까지 꽤 어려운 문제였다.
참고로 위 8~19번째 줄의 코드(아래 첨부)를 빠뜨리면 시간 초과가 발생한다.
if a + b + c > N:
break
저 코드 2줄이 있고 없고의 차이가 시간 복잡도에 큰 영향을 준다. 왜 그런지는 스스로 고민해보자.
'알고리즘과 자료구조 > Dynamic Programming' 카테고리의 다른 글
| Dynamic Programming 5: DP 배열 설정의 중요성 (백준 14238, 17404, 12969번) (0) | 2023.04.03 |
|---|---|
| Dynamic Programming 4: 배낭 문제 (백준 7579, 2629번 파이썬) (0) | 2023.03.29 |
| Dynamic Programming 3: 재귀(top-down)를 이용한 풀이 (백준 11049번 파이썬) (0) | 2023.03.29 |
| Dynamic Programming 2: 재귀(top-down) vs. DP(bottom-up) (백준 11066, 1520, 1937번 파이썬) (0) | 2023.03.28 |
| Dynamic Programming 1: 기초 풀이 접근 (백준 10942, 17070번) (0) | 2023.03.28 |
