문제
https://www.acmicpc.net/problem/14238
요즘 너무 브~실 문제만 푼 것 같아서, 문법은 그때그때 검색하며 익히기로 하고, 다시 골드로 회귀했다.
백준을 그만두기 전, 가장 좋아했던 분야가 DP였기에 DP 랜덤 골드 문제를 하나 골랐는데, 결론부터 말하면 푸는 데엔 실패했다.
그래서 이번엔, 풀이보단 일종의 학습 기록이 될 것 같다. 풀이가 궁금하다면 아래 블로그를 참고하자. 설명이 잘 되어 있다. 나도 이 블로그를 바탕으로 공부할 예정이고.
Dynamic Programming 5: DP 배열 설정의 중요성 (백준 14238, 17404, 12969번 파이썬)
백준 14238번: 출근 기록 문제 설정은 간단하다. 각 알파벳 A, B, C에 대해서 아래 조건을 금방 파악할 수 있다. 그렇지만 문제 조건을 잘 파악했다 하더라도 다음이 문제다. 기존 문제처럼 dp 배열이
seanshkim.tistory.com
1. 학습 과정
기본적으로 블로그를 바탕으로 학습하며, 중간에 궁금증이 생기면 Gemini에게 물어보는 식으로 학습한다.
기본 배경 (문제 풀이 시도)
풀이를 보지 않고 시도했을 땐, 그리디한 백트래킹을 이용한 방법만이 떠올랐었다. C, B, A 순서대로 고르며, 만약 고를 수 없다면 이전으로 돌아간다.
여기엔 몇 가지 문제가 있었는데, 근원적으로 말하면 최적해를 찾을 수 없었다.
쉬운 DP 문제는 조건이 아주 명확하다.
- 이전 값은 무슨 일이 있어도, 현재 시점에선 변하지 않으며
- 현재 시점에 선택, 혹은 계산에 사용할 값도 고정되어 있으며
- 미래와 관계가 없다.
예를 들면 피보나치 같은 거다. f(n-1)은, n이 주어진 상황에선 항상 동일한 값을 가진다. n 역시, 무슨 일이 있어도 변하지 않으며, f(n)이 미래 상황에 의해 달라지는 경우도 발생하지 않는다.
하지만 이번 문제가 어려운 건, 위 조건을 지키지 않기 때문이다.
- 현재에 따라 과거의 정답이 달라질 수 있다. 현재 시점에서, 고를 수 있는 카드가 C, B, A 중 뭐가 남았냐에 따라, 골라야 하는 dp[n-1]이 달라진다.
- 현재 시점에 선택할 값 역시 고정되어 있지 않다. 이는 과거와 연결되며, 과거 기록과 현재 남은 개수에 따라 C, B, A 중 무엇을 골라야하는지가 정해진다. (못 고른다는 선택지도 있다.)
- 미래와도 긴밀하게 관계된다. 만약 여기서 C를 골랐는데, 남은 게 BC라면? 지금의 선택을 번복해야 한다. 때에 따라 더 과거 시점으로 거슬러가기도 한다. 백트래킹처럼. (사실 BCC 남았으면 이미 잘못된 거긴 하다)
즉, 포뻥도 안 채우고 발드릭스에 도전했다고 해야 하나... 경험치가 덜 쌓였는데 무턱대고 어려운 걸 붙잡은 상황. 사실 시간을 무한대로 줬어도 풀긴 어려웠을 거다. 하나 다행인 점이라면, 어려운 문제를 분석할 때 실력이 많이 오른다는 점일까?
블로그 학습
Sehyun님의 블로그에선 DP에 쓸 차원에 따라, 문제를 풀 수 있는가를 다루며, 1차원부터 5차원까지 늘어나는 과정을 설명하고 있다.
즉, 이 문제는 5차원 DP로 풀어야하며, 이걸 모른다면 풀 수 없는 상황. 이때 궁금한 점이 생겨 AI에게 질문을 던졌다.
AI 질문
내용을 요약 및 재해석하면, 이렇게 볼 수 있다.
dp 배열에 저장하는 건, 판단의 기준이 되는 데이터다.
피보나치의 경우, 현재 칸을 결정하는 건 앞의 두 수다. 이는 연속된 공간이고, 동일하게 만들어진 데이터이기에 1차원 배열로 나타낼 수 있다. 그래서 1차원 배열 DP로 피보나치를 풀 수 있다. 보통 피보나치의 경우, 저장된 데이터를 곧 정답으로 써먹기에 추가적인 칸(변수)도 필요 없다.
2번의 제약 조건 역시, 넓게 보면 결정 요소 중 하나다. 과거에 해당 행동을 했었는지 여부를 데이터로 따로 저장해두는 것.
여기서 중요한 건, 차원을 늘리는 건 표의 줄을 늘리는 것과는 다르다는 거다. 새로 추가된 차원은, 그전까지의 값 전체에 대해 추가되는 것이다. 4차원 이상은 그림으로 만들어 이해하는 게 더 어렵기에, 추상적으로 이해하는 게 더 도움이 된다.
다시 블로그로
이번 문제는 A, B, C의 각 개수, B를 사용했는지 여부, C를 사용했는지 여부가 필요하다. 후자는 다르게 보면 이전 2칸의 문자열이 필요한 거고, 이를 각각, 이전 문자와 2번째 전 문자로 저장한 것이기에, 5차원 배열이 필요하게 되었다.
dp[a][b][c][p1][p2] -> 출근 기록 순열 (총 길이는 a + b + c)
a: 알파벳 A의 개수
b: 알파벳 B의 개수
c: 알파벳 C의 개수
p1: 마지막 문자 (A: 0, B: 1, C: 2)
p2: 끝에서 2번째 문자
로 두고, Sehyun님은 문제를 푸셨다. 예를 들어, dp[1][3][2][1]라면, A가 1개, B가 3개, C가 2개이고, 끝에서 2번째가 B인 순열이다. 이때, 값으로 저장하는 건 문자(A, B, C)다.
Sehyun님의 코드를 반쯤 따라치고, 약간 다듬어서 아래와 같이 만들어보았다.
import sys
input = sys.stdin.readline
records = input().rstrip('\n')
A, B, C = 0, 1, 2
count = [records.count('A'), records.count('B'), records.count('C')]
# 배열 생성 (크기 할당)
# dp[A의 개수][B의 개수][C의 개수][끝에서 2번째 글자][끝 글자]
dp = [[[[
[''] * 3
for _ in range(3)]
for _ in range(count[C] + 1)]
for _ in range(count[B] + 1)]
for _ in range(count[A] + 1)]
# 초기 값 설정
for prev2 in range(3):
if count[A] > 0:
dp[1][0][0][prev2][A] = 'A'
if count[B] > 0:
dp[0][1][0][prev2][B] = 'B'
if count[C] > 0:
dp[0][0][1][prev2][C] = 'C'
# DP 실행
for a in range(count[A] + 1):
for b in range(count[B] + 1):
for c in range(count[C] + 1):
for prev2 in range(3):
for prev1 in range(3):
# 이전 순열이 존재하지 않는다면 스킵
if dp[a][b][c][prev2][prev1] == '':
continue
# 1. A 추가 (제약 없음)
if a < count[A]:
# 마지막 문자가 A가 되니, 끝 글자는 2번째 전 글자가 된다. (prev2, prev1 -> prev1, A)
dp[a+1][b][c][prev1][A] = dp[a][b][c][prev2][prev1] + 'A'
# 2. B 추가 (끝 글자가 B가 아니어야 함)
if b < count[B] and prev1 != B:
dp[a][b+1][c][prev1][B] = dp[a][b][c][prev2][prev1] + 'B'
# 3. C 추가 (끝 2개 글자가 C가 아니어야 함)
if c < count[C] and prev2 != C and prev1 != C:
dp[a][b][c+1][prev1][C] = dp[a][b][c][prev2][prev1] + 'C'
def solution():
# 수많은 dp[A][B][C] 배열 중, 문자열이 존재하면 바로 리턴
for prev2 in range(3):
for prev1 in range(3):
if dp[count[A]][count[B]][count[C]][prev2][prev1] != '':
return dp[count[A]][count[B]][count[C]][prev2][prev1]
# 없으면 -1
return -1
print(solution())
for문이 많이 중첩되어 알아보기 힘든데, for a, for b, for c는 한 덩어리로 묶어서 모든 경우의 수로 보면 조금 편해진다.
A가 3개, B가 7개, C가 5개 있다면, dp[0][0][0]부터 dp[3][7][5]까지, 모든 경우의 수를 찾아보는 것.
모든 조건은 인자로 다룬다. dp[a][b][c][prev2][prev1]에서
a = 지금껏 사용한 A의 개수, b = 지금껏 사용한 B의 개수, c = 지금껏 사용한 C의 개수
prev2 = 끝에서 2번째 자리 문자, prev1 = 마지막 자리 문자이며
그 값으로 들어가는 건 완성된 순열이다.
이해하기 쉽게 예를 들어보면, dp[1][2][1][B][C] = 'BABC' 같은 상황이다.
for문 속 a는 0부터 count[A]개까지 넣어보기 위한 반복자고, prev2, prev1은 A, B, C를 하나씩 넣어본다(range(3) = [0, 1, 2] = [A, B, C]고 볼 수 있다.
코드
import sys
input = sys.stdin.readline
records = input().rstrip('\n')
A, B, C = 0, 1, 2
count = [records.count('A'), records.count('B'), records.count('C')]
# 배열 생성 (크기 할당)
# dp[A의 개수][B의 개수][C의 개수][끝에서 2번째 글자][끝 글자]
dp = [[[[
[''] * 3
for _ in range(3)]
for _ in range(count[C] + 1)]
for _ in range(count[B] + 1)]
for _ in range(count[A] + 1)]
# 초기 값 설정
for prev2 in range(3):
if count[A] > 0:
dp[1][0][0][prev2][A] = 'A'
if count[B] > 0:
dp[0][1][0][prev2][B] = 'B'
if count[C] > 0:
dp[0][0][1][prev2][C] = 'C'
# DP 실행
for a in range(count[A] + 1):
for b in range(count[B] + 1):
for c in range(count[C] + 1):
for prev2 in range(3):
for prev1 in range(3):
# 이전 순열이 존재하지 않는다면 스킵
if dp[a][b][c][prev2][prev1] == '':
continue
# 1. A 추가 (제약 없음)
if a < count[A]:
# 마지막 문자가 A가 되니, 끝 글자는 2번째 전 글자가 된다. (prev2, prev1 -> prev1, A)
dp[a+1][b][c][prev1][A] = dp[a][b][c][prev2][prev1] + 'A'
# 2. B 추가 (끝 글자가 B가 아니어야 함)
if b < count[B] and prev1 != B:
dp[a][b+1][c][prev1][B] = dp[a][b][c][prev2][prev1] + 'B'
# 3. C 추가 (끝 2개 글자가 C가 아니어야 함)
if c < count[C] and prev2 != C and prev1 != C:
dp[a][b][c+1][prev1][C] = dp[a][b][c][prev2][prev1] + 'C'
def solution():
# 수많은 dp[A][B][C] 배열 중, 문자열이 존재하면 바로 리턴
for prev2 in range(3):
for prev1 in range(3):
if dp[count[A]][count[B]][count[C]][prev2][prev1] != '':
return dp[count[A]][count[B]][count[C]][prev2][prev1]
# 없으면 -1
return -1
print(solution())
원본 코드와 비교하면 차이점은 다음과 같다.
- A = 0, B = 1, C = 2로 값을 넣어두어 코드를 보기 편하게 만들었다. 이게 의외로, 인자에 A, B, C처럼 적을 수 있어 가독성을 많이 올린다. (초기값 설정을 원본과 비교해보자.)
- numA, numB, numC로 적은 걸 count로 묶음 conut[A] = count[0] = numA = A의 개수가 된다.
- Sehyun님은 배열 인자 순서를 [끝 글자][끝에서 2번째 글자]로 두셨지만, 나는 이걸 [끝에서 2번째 글자][끝 글자]로 두어, 순열의 맨 뒤 2자리를 잘라낸 듯 만들었다.
- Sehyun님의 방식이라면, CBACB라는 문자열은 dp[1][2][2][B][C]에 들어간다. 나는 이걸 dp[1][2][2][C][B]로 옮겼다.
- 이로써 초기 값 설정 시, 왜 저 위치에 'A', 'B', 'C'가 들어가는지 직관적으로 이해 가능하다.
- DP 실행 시, Sehyun님은 3번의 반복문 후 조건문을 걸어, A, B, C를 사용한 모든 경우의 수에서 A, B, C를 넣는 경우를 나누고, 그 if 속에서 for문을 통해 모든 곳에 값을 채워넣는, 작성할 때 직관적인 방법을 사용하셨다.
- 나는 여기에 더해, 끝 글자 조합도 고정시킨 상태에서 A, B, C를 넣어보았다. 이 부분은 Gemini가 추천해준 방식인데, 나는 고차원 DP를 다뤄보는 게 처음이라, 코드를 읽을 땐 이쪽이 더 보기가 쉬워 선택했다. for문 중첩 중간에 자르고, 로직에 맞춰 또 for문을 중첩하는 게 처음 코드를 읽을 때 해석이 어려웠었다.
- 더불어 이전 칸이 비었는가란 조건을 맨 위에 옮겨 1번만 작성됐고, 원본 코드는 이전 값을 비교해 현재에 넣으셨고, 이 코드는 현재 값을 비교해 다음 칸에 채워넣었다. 이로써 a > 0이라는 조건을 검사할 필요가 사라졌다.
결과
내가 만든 코드는 아니기에 비공개로 올렸다. 코드를 수정하며 로직이 꼬인 부분이 있었을까 싶어 넣었는데, 다행히 아무 문제 없었다.
개선
사고 과정
구조를 이해하고 나니 5번 중첩된 for문도, 5차원 배열도 이해하는데 문제가 없어졌다. 각 for문에서 무슨 일이 벌어지는지도 사실 알 필요 없고, 5차원 배열이 전체적으로 어떤 형태를 띄는지도 몰라도 된다. 5차원 배열의 각 차원은 그저 하나의 조건을 성립시킨 경우의 수로 써먹으면 되고, 5차원 for문 역시 모든 경우를 돌아보며 한다는, 하나의 뜻만 갖고 있었다.
그럼에도, 만약 재귀를 쓴다면 더 간결하게 나타나지 않을까?라는 생각을 했고, Gemini에게 이 코드를 재귀로 바꿔달라고 요청하였다.
코드
import sys
sys.setrecursionlimit(10**6) # 재귀 깊이 제한 해제
input = sys.stdin.readline
records = input().rstrip('\n')
A, B, C = 0, 1, 2
count = [records.count('A'), records.count('B'), records.count('C')]
total_len = len(records)
# memo[a][b][c][prev2][prev1]
# 방문 여부와 실패 기록을 동시에 관리하기 위해 -1로 초기화
memo = [[[[[-1] * 3
for _ in range(3)]
for _ in range(count[C] + 1)]
for _ in range(count[B] + 1)]
for _ in range(count[A] + 1)]
ans = [''] * total_len
def solve(a, b, c, prev2, prev1):
# 모든 문자를 다 사용했으면 성공!
if a == count[A] and b == count[B] and c == count[C]:
return True
# 이미 방문한 적이 있다면 (성공했다면 이미 끝났을 것이므로 여기는 항상 실패 경로)
if memo[a][b][c][prev2][prev1] != -1:
return False
# 1. A 추가 (제약 없음)
if a < count[A]:
ans[a + b + c] = 'A'
if solve(a + 1, b, c, prev1, A): return True
# 2. B 추가 (prev1 != B)
if b < count[B] and prev1 != B:
ans[a + b + c] = 'B'
if solve(a, b + 1, c, prev1, B): return True
# 3. C 추가 (prev2 != C and prev1 != C)
if c < count[C] and prev2 != C and prev1 != C:
ans[a + b + c] = 'C'
if solve(a, b, c + 1, prev1, C): return True
# 이 경로로는 정답을 찾을 수 없음을 기록
memo[a][b][c][prev2][prev1] = 0
return False
def solution():
# 초기 호출: prev2와 prev1에 A, B, C가 아닌 가상의 값(예: 0~2 외의 값)을 넣어 초기 제약 통과
# 여기서는 안전하게 시작하기 위해 처음 두 글자가 C나 B가 아닌 상태로 시작합니다.
# (반복문의 초기값 설정 로직을 재귀적으로 표현)
# 실제로는 '아무것도 안 뽑은 상태'를 의미하는 인덱스가 필요하므로
# memo 크기를 3이 아니라 4로 잡거나, 시작할 때만 예외 처리를 합니다.
# 편의상 A(0)가 아닌 다른 값 3을 초기값으로 사용하겠습니다. (memo 인덱스 조절 필요)
# memo 인덱스 범위를 위해 0, 1, 2 중 C나 B가 아닌 것으로 시작하거나
# memo를 [][][][4][4]로 선언하는 것이 가장 깔끔합니다.
return solve(0, 0, 0, A, A) # 초기 상태를 A, A로 가정해도 A 추가 로직엔 문제 없음
# memo를 초기값(여유분 4)을 포함해 다시 정의
memo = [[[[[-1] * 4 for _ in range(4)] for _ in range(count[C] + 1)] for _ in range(count[B] + 1)] for _ in range(count[A] + 1)]
if solve(0, 0, 0, 3, 3): # 3은 '없음'을 의미
print("".join(ans))
else:
print("-1")
확실히 재귀가 로직은 깔끔하게 나온다. for문을 안 쓰니 보기도 편하고.
결과
대신 메모리 초과가 났다. 역시 코테엔 얌전하게 반복문을 쓰자.
강평
다차원 DP가 이렇게 쉽고 재밌을 줄은 몰랐다.
예전에 학교 대회에서 3차원 DP 문제가 나왔을 때나, 알고리즘 스터디에서 2차원 DP를 전부 그려서 올린 풀이를 봤을 땐, "다차원 DP가 어렵고 복잡하구나."라고 생각했었다. 그런데 오늘 문제와 풀이를 뜯어봤을 때, 생각보다 쉽고, 간단하고, 재밌어서 놀랐다. Sehyun님이 글을 잘 쓰셔서 그런가?
사실 원래는 다익스트라 같은 그래프 문제를 풀까 했었다. 알고리즘 문제를 풀때 그리디, DP, 수학, 백트래킹이나 브루트포스 같은 직관적인 영역은 좋아하고, 그래프는 편식을 했었기에.... 그런데 이왕 하는 거, 재밌고 좋아하는 DP를 끝까지 정복한 후 다른 분야로 가보면 어떨까? 싶은 생각이 들었다. DP 플래티넘까지 올라간 후에, 다른 분야를 하나씩 시작하는 게 더 재밌어보였다.
그런 점에서 다차원 DP를 써본 건 이번이 처음인데, 생각보다 훨씬 직관적이고 간단한 방법이라 놀랐다. 기존엔 3차원 DP 같은 문제를 볼 때, 배열 전체를 그릴 수 있게 되면 풀 수 있을 거라 생각했는데, 전혀 아니었다. 오히려 배열에 무슨 값이 들어가서, 어떻게 진행되는지는 안 봐도 되고, 하나의 차원을 하나의 조건으로 쓴다는 알고리즘이 마음에 들었다. 이번엔 최초 학습인 만큼 다른 분의 코드를 뜯어보며 학습했지만, 이다음 문제는 스스로 풀어내고 싶다.
옛날 생각이 난 김에, 과거 풀이 중 가장 인기 많았던 것도 올려둬야겠다. 돌아봤을 때, 가장 나다운 풀이였다고 생각한다.
11-miniron-v by miniron-v · Pull Request #43 · AlgoLeadMe/AlgoLeadMe-5
🔗 문제 링크 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 분류: 백트래킹, 브루트포스 ✔️ 소요된 시간 40분 ✨ 수도 코드 먼저 가장 Naive한 방법부터 살펴보겠습니다. 엄청난 풀이가 필요하
github.com
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준/Python3] 12015번. 가장 긴 증가하는 부분 수열 2 - 가장 쉬운 원리 이해 (0) | 2026.02.13 |
|---|---|
| [백준/Python3] 25419번. 정수를 끝까지 외치자 (0) | 2026.02.11 |
| [백준/Python3] 1105번. 팔 (0) | 2026.02.06 |
| [백준/Python3] 1024번. 수열의 합 (0) | 2026.02.02 |
| [백준/Python3] 1018번. 체스판 다시 칠하기 (0) | 2026.01.31 |