문제
https://www.acmicpc.net/problem/25419
알고리즘 문제는 매일 풀고 있지만, 그때마다 항상 블로그를 쓰진 않았다.
이전에 비슷한 걸 풀어서 쓸만한 내용이 없거나, 혹은 이동 중에 휴대폰으로 풀 때도 있어 글을 쓸 환경이 아닐 때도 있었으니까.
그래서 DP 문제를 여럿 풀면서, 원래대로라면 풀기만 하고 올릴 생각은 없었는데... 꽤 골때리는 문제를 만나 이렇게 포스팅한다.
1. 첫 번째 풀이
사고 과정
가장 처음까지 돌아가면, 문제 조건이 엄밀하지 않아서 애를 먹었었다. 잘못 만든 문제다 이거.
문제엔 단순히 "두 명의 학생이 규칙에 맞게 플레이했을 때"라고만 쓰여 있는데, 정확히는 최선의 방법으로 플레이했을 때가 되어야 한다. (대충 플레이하면 정답은 0일 수도, 1일 수도 있는 슈뢰딩거의 정답이 된다.)
아주 단순한 베스킨라빈스 게임이었다. 한명당 3개씩 숫자를 외치고, 31을 외치는 사람이 지는 게임.
이 문제는 N과 K가 주어지면, 1부터 K까지, 원하는 만큼 외치는 게임. 하나 다른 점은 마지막 숫자를 외쳐야 승리라는 건데, 아마 계산 상의 이유로 이게 편했겠거니 하고 넘겼다.
당연히, 맨 처음 생각한 건 무조건 이기는 수를 외치는 것이었다. 베스킨라빈스 게임을 해본 사람은 알겠지만, 2명이 진행하고 31을 외쳐야 승리하는 경우라면, 나는 27을 외쳐야 한다. 그래야 상대가 28, 29, 30중 무엇을 외쳐도, 내가 31을 외칠 수 있으니까.
상대가 1칸 앞으로 가면, 나는 3칸 앞으로 간다. 상대가 3칸 앞으로 가면, 나는 1칸 앞으로 간다. 나는 어떤 상황에서도 4칸 앞을 선점할 수 있다. 문제에 맞게 변형하면, k + 1칸을 선점할 수 있다.
문제는, 외칠 수 없는 수의 존재다. 말 그대로 해당 수는 외칠 수 없게 된다. 만약 무조건 이기는 수가 막혀버린다면. 이 상황에서 문제가 발생했다.
처음엔, 그런 경우 그 앞 칸을 선점하면 된다 생각했다. 27이 막혔다면, 26을 외치면 되지 않는가. 그럼 27은 어차피 막혀서 외칠 수 없고, 상대는 28과 29 중 하나를 골라야 한다. 그럼 나는 29, 30, 31을 외칠 수 있으니, 어떤 경우든 이길 수 있다.
그런 식으로 생각을 이어가던 중, 문득 이런 생각이 떠올랐다. 지금 돌이켜보면, 탑다운 방식이 마음에 안 들었던 것도 같다.
- 1 ~ k를 내가 선점한다. (1로 표시)
- 1부터 n까지 반복문을 돌리며, 현재 위치(i)가 1일 경우, i + k + 1칸을 선점한다. (나는 해당 수를 항상 외칠 수 있다.)
- 이걸 끝까지 반복한다.
- dp[n]을 출력한다. 해당 칸이 외칠 수 없는 칸일 경우, 그 앞 칸을 외칠 수 있다면 승리한다.
i + k + 1만 선점한 이유는, 그 주변 칸은 상대가 최선을 다하면 선점 가능한 수기 때문이다. k = 3이라면, 상대가 1~3, 내가 1~3, 총 6칸이 존재하는데, 5번째 칸은 상대가 1을 외치면 내주어야 하고, 6번째 칸 역시 상대가 2를 외치면 내주어야 한다. 따라서, 내가 무조건 먹을 수 있는 건 오직 4번째 칸이 유일했다.
뭔가 될 것 같았고, 그대로 코드를 작성했다.
코드
n, k = map(int, input().split())
ban = list(map(int, input().split()))
# 초기 값 설정
dp = [0] * (n + 1)
for i in range(1, k+1):
dp[i] = 1
for i in ban:
dp[i] = -1
# dp 돌리기
for i in range(1, n+1):
if dp[i] == 1 and i + k + 1 <= n and dp[i + k + 1] != -1:
dp[i + k + 1] = 1
while dp[n] == -1:
n -= 1
# 출력
print(dp[n])
초기 값은 0, 1~k는 1, 외칠 수 없는 수는 -1로 덮어씌운다. n이 1이면 이기고, 0이면 질테니 그대로 출력한다.
결과
하지만 조금 올라가다 틀렸습니다가 떴다. -1로 처리된 칸이 문제를 일으켰다는 건 금세 알 수 있었다.
2. 두 번째 풀이
사고 과정
질문 게시판의 반례와 함께 코드를 돌아봤는데, 내가 놓친 건 다음 케이스들이었다.
먼저, -1이 k칸 연속되는 경우다. 그 경우, -1이 나오기 직전 칸이 승리 칸이 되며, 그곳을 선점해야 한다.
인지는 하고 있었지만, 굳이 따로 빼야 하나? 싶었는데, 내 경우, 이런 곳을 지나치면 이후가 전부 0으로 완성된다. 그러나 n이 바뀌지 않았기에, 이 구간 이후에서 계산을 하려니 틀린 정답이 나온다.
두번째는, 이런 케이스다.
[0 -1 0 -1 -1 0], N = 6, K = 3인 경우
내 방식대로면, 먼저 1~k까지 선점하므로 [1 -1 1 -1 -1 0]이 되고, 6을 외칠 방법은 없기에 진다.
하지만, 내가 1을 외친다면, 상대는 3을 외쳐야만 하고, 나는 6을 외칠 수 있다. 이런 경우를, 내 코드론 케어할 수 없다.
여기서 로직 자체가 잘못되었음을 느꼈고, 새로운 풀이를 강구해봤다. 그러나 아무리봐도 다차원 DP를 쓸 문제는 아니었다. 최선의 수를 둔다는 점이 발목을 잡았다.
결국, DP보단 게임 이론에 더 치중된 문제라고 느꼈고, 풀이 방법을 찾아보기 시작했다. 대부분 탑다운 방식으로 해결하였다.
이르자면, N에 도달하기 위해 선점해야 하는, 가장 작은 필승 수를 알아내야 하는 문제다. 그를 위해 N에서부터 역으로 거슬러 올라갔고, 만약 그 수가 내가 시작하자마자 외칠 수 있는 수라면, 이긴다. 같은 느낌이다.
그래서 우선, 나도 탑다운 방식으로, 가장 작은 필승 수를 알아내려 해보았다.
모든 수를 외칠 수 있다면 방법은 단순하다. n에서 (k + 1)을 계속 빼면 되니까. 더 쉽게는 N % (K + 1)만 해도 된다.
문제는, 외칠 수 없는 수의 존재다. 31부터 거슬러 올라가면서, 여러 상황들을 찾아보자.
1. 27만 외칠 수 없는 경우
31을 외쳐야 하는데 27을 외칠 수 없다면, 나는 26을 외쳐야 한다. 본래라면 상대가 27을 외치며 끝날 상황이지만, 상대는 27을 외칠 수 없기에, 28이나 29를 외쳐야 하고, 내가 승리한다.
2. 26, 27을 외칠 수 없는 경우
26마저 외칠 수 없다면, 나는 25를 외쳐야 한다. 그럼 상대가 외칠 수 있는 건 28만 남고, 내가 승리한다.
3. 27, 29를 외칠 수 없는 경우
상대가 28, 혹은 30을 외쳐야 하므로, 나는 역시나 26을 외쳐야 한다. 즉, 외칠 수 없다면 그 앞 칸이 승리라는 조건은 유효하다.
그럼 다시, 로직만 살짝 바꿔서, 뒤에서부터 거슬러 올라가게 해보자.
코드
n, k = map(int, input().split())
ban = list(map(int, input().split()))
# 초기 값 설정
dp = [0] * (n + 1)
for i in range(1, k+1):
dp[i] = 1
for i in ban:
dp[i] = -1
# k칸 연속 막힌다면, 막히기 직전 수를 외쳐야 이긴다.
for i in range(n - k):
# [i:i + k]가 모두 -1이었다면
if sum(dp[i:i + k]) == k * -1:
n = i - 1
break # 어차피 반복문이 끝나겠지만, 혹시 모르니 안전하게...
# dp 돌리기 (가장 작은 필승 수 찾기)
while k < n or dp[n] == -1:
if dp[n] == -1:
n -= 1
else:
n -= k + 1
# 출력
print(dp[n])프로그램 코드
결과
결과는 70점. 서브태스크라는 문제는 처음보는데... 아무튼 100점은 아닌 거겠지?
배점은 이렇겐데, 그럼 1 <= n, k <= 20에서 틀렸다는 소리. 그정도면 70점이라도 맞은 게 운 좋게 오류가 안 나서라고 봐야하는 거 아닐까?
3. 마지막 풀이
사고 과정
Gemini에게 반례를 찾아달라했는데, 반례는 커녕 올바른 답도 찾아내지 못했다.
Gemini가 제시한 DP 조건은 이렇다.
상대가 외칠 수 있는 i + 1부터 i + k 안에 하나라도 필승석이 있다면, 내가 진다.
그러니 필승석이란 건, 다음 구간에 필승석이 없는 것만이 필승석이 된다.
그러기 위해선 맨 뒤에서부터 DP를 채워나가야 한다. 우선, 연속된 금지 구간(k = 3인데 -1 -1 -1인 경우)은 잘라내고 시작한다. 이 경우에도, 구간 직전 수를 N으로 변경한다 하자.
N은 필승석이다. 그렇기에, N이 포함되는 N - 1, N - 2, ..., N - K 구간은 전부 패배석이 된다.
그러면, N - K - 1 칸은 다시 필승석이 된다. (N -1, N - 2, ..., N - K 구간 모두 패배석일 테니)
다시, 이전 칸으로 돌며, 필승석이 없는 칸에만 필승석으로 표시한다. 해당 칸이 -1로 막혀버렸다면, 그 앞 칸이 필승칸이 된다.
...적고보니 내가 짠 코드와 로직이 똑같다. N - 1부터 N - K까진 항상 패배석이니, N - K - 1부터 찾아봐야 한다.
만약 거기가 필승석이 된다면, 다시 거기부터 i - 1부터 i - K까진 패배석이니 건너뛸 것이고, 만약 거기가 -1이라면, 그 앞이 필승석이 되므로 한칸 앞으로 이동한다.
오히려, 내가 짠 코드가 불필요한 구간 검사를 생략해, 더 효율적이다.
그래서, 이번엔 다른 분의 코드와 내 코드를 직접 비교하며 차이점을 찾아보았다.
25419 정수를 끝까지 외치자 (백준, python3)
시간 제한메모리 제한1초512MB문제두 명의 학생이 1이상 n이하의 정수를 외치는 게임을 하고 있다. 첫 번째 학생이 먼저 정수를 외친 후 두 명의 학생이 교대로 정수를 외친다. 이
celbeing.tistory.com
로직에서 가장 큰 차이점은 아래와 같다.
내 로직
1부터 K까지 1로 칠해놓고, 필승 수가 이 범위 내로 들어오면 성공한다.
N부터 시작해, N - K - 1을 필승 수로 지정한다. 장애물이 있다면 그 앞 칸을 필승 수로 지정한다.
내가 패배하는 경우: 마지막에 출력한 필승 수가 0일 경우
윗분의 로직
N에서 시작, 필승 수를 찾아 전부 1로 칠한다.
1부터 K 중, 하나라도 필승 수가 있다면 승리한다. 그 외라면 패배한다.
그래서, 저분의 로직처럼, 뒤에서부터 필승 수를 모두 채우고, 내가 그 수를 바로 외칠 수 있으면 정답으로 바꿨다.
테스트
그래서 코드를 서로 비교하고, 합쳐보며 문제를 찾아보았다. 내 코드로는 70점이 한계고, 저분의 로직을 응용하면 100점을 맞을 수 있었다. 문제는 2가지나 있었다. 70점 맞은 게 기적
1. 막힌 구간 탐지의 문제
먼저, 막힌 구간을 탐색할 때 문제가 있었다.
내 코드는 sum(dp[i:i+k]) == k * -1로 벽을 탐지했는데, 맨 끝부터 k 미만 칸으로 연속된 경우를 못 잡고 있었다. (...) 게다가 슬라이싱으로 인해, 속도도 많이 느렸다.
이는 아예 맨 뒤에서부터, 연속된 -1을 카운팅하고, 그게 k개가 되면 n을 옮기는 방식이 더 안정적이고 빨랐다.
2. 로직의 문제
두번째는 로직 자체의 문젠데, 단순히 N -= K + 1로 점프하는 방식은, 잠재적인 오류를 떠안고 있다.
그 원리를 알아내려 Gemini에게 문제 설명과 코드를 보여주며 질문했는데, Gemini는 로직을 이해하지 못하고 틀린 답변만 계속 늘어놓았다.
(아마 LLM의 원리가 스스로 해석하고 추론하는 게 아닌, 본인이 학습한 데이터 중 가장 유사한 것을 내놓는 방식이기 때문이 아닐까 싶다. 적어도 구글에서 한글로 찾아본 바로는, 그 이유를 설명한 글이 없었다.)
그래서 질문 방식을 조금 바꾸어, LeetCode에서 이와 동일한 문제를 찾고, 해당 문제에 대한 질문글들 중 "왜 수식으로 계산하면 답이 틀리나요?"를 찾아, 그 답변 글을 한글로 번역해달라고 요청했다. 그렇게 나온 결과는 아래와 같다.
범위를 넓혀, 해외 모든 사이트 중 장애물이 있는 Nim Game 관련으로 범위를 넓히면, 아래처럼 나온다.
결과적으로, 얼핏 보면 수학적으로 풀릴 것 같으나, 주기성이 파괴되어 예측 불가능한 영역에 도달한다.는 결론이 된다.
솔직히 무슨 소리인지는 반례가 없어 이해하기 힘든데, 대강 앞에서부터 주기적으로 필승 카드를 찾아다녔다고 했을 때, 장애물에 의해 막힌 경우, 그 뒤쪽도 기존/혹은 변형된 주기를 따라간다고 증명할 수 없다.고 이해하는 게 최선 같다. 실제로 반례를 찾지 못했을 뿐, 백준엔 분명 이 반례가 되는 테스트 케이스가 존재한다.
결국 여기서 한계를 느끼고, 최종 코드를 정리했다.
코드
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
ban = list(map(int, input().split()))
# 초기 값 설정
dp = [0] * (n + 1)
for i in ban:
dp[i] = -1
# 막힌 구간을 찾아, 그 앞칸을 목적지로 지정한다.
count = k
for i in range(n, -1, -1):
if dp[i] == -1:
count += 1
else:
if count >= k:
n = i
count = 0
# 목적지는 외치면 이기는 필승 칸이다.
dp[n] = 1
# # dp 돌리면서 채우기
for i in range(n - 1, 0, -1):
if dp[i] == -1:
continue
# 뒤의 k이 모두 패배 칸이면 1(필승 칸)을, 아니면 0(패배 칸)을 기입한다.
dp[i] = 1 if all(dp[j] < 1 for j in range(i + 1, min(i + k, n) + 1)) else 0
# 출력
can_win = 0
# 하나라도 필승 칸을 먹을 수 있다면 이긴다.
for i in range(1, min(n, k) + 1):
if dp[i] == 1:
can_win = 1
break
# 출력
print(can_win)
코드를 직접 만들고, 변형하고, 붙여보며 4시간 정도 혈투 끝에, 이제야 괜찮은 코드가 나왔다.
하면서 느낀 점은 아래 회고에서 다뤄야겠다.
결과
회고
사고 과정
오래간만에 문제 풀면서 머리 아픈(물리적) 문제였다.
먼저, 몇 가지 시행 착오를 살펴보자.
1. rstrip을 붙이면 틀린다.
readline의 끝엔 개행문자('\n')가 붙기에, input에 함수를 덧씌우는 과정에서 rstrip까지 한번에 연결해보려 했었다.
결론부터 말하면, 아무도 안 하는덴 이유가 있더라.
여기서 꽤 많은 잘못된 코드를 만들었었는데, 하나씩 살펴보자.
먼저 원본이다.
올바른 코드: input = sys.stdin.readline
이 코드는 파이썬의 함수 참조를 이용한 코드로, 이제부터 input()을 실행하면 sys.stdin.readline()가 실행된다.
input에 함수 자체를 담은 것이다.
이제 틀린 코드를 하나씩 살펴보자.
1. input = sys.stdin.readline()
뭐가 틀렸냐 하면, 마지막에 괄호를 붙인 게 틀린 거다.
괄호가 붙었기 때문에, 이 코드는 input이란 변수에 함수 실행 결과를 담는 로직이 됐다. (여기서 입력을 한번만 받는다.)
따라서, 이후 input()을 작성하면 str은 collectable하지 않습니다 (대충 괄호 못 붙인단 뜻)라는 에러가 뜬다. input으로 쓰면 문자열이 나오니... (이하 생략)
2. input = sys.stdin.readline.rstrip
rstrip은 str의 함수이다. sys.stdin.readline()의 결과가 문자열이기에 rstrip을 쓸 수 있는 거지, 저 상태로는 쓸 수 없다. 당연히 함수 참조도 아니다.
3. input = sys.stdin.readline().rstrip
문법적으론 문제가 없지만, 1과 동일하다. readline 한 결과물에 rstrip을 붙인 거기에, 문제가 된다....
결론은 input = sys.stdin.readline만 쓰고, rstrip은 따로 쓰거나, 혹은 쓰지 말자는 거다.
특히 정수 입력의 경우엔, 어차피 map 함수가 개행 문자를 제거해주니 굳이 rstrip 쓸 필요도 없다. 문자열 다룰 때나 따로 붙여줘라.
2. 문제를 보며 생각한 로직을 정확히 구현하자.
나는 보통 수학 문제도 그렇고 다른 문제도 그렇고, 사례에서 규칙을 찾는 귀납적 추론을 습관처럼 사용한다. 이번 문제 역시, N과 K를 여러 가지로 지정해서 로직을 돌려본 후, N - K - 1은 무조건 필승 칸이네? 벽을 만나면 한 칸 앞이 필승 칸이 되네?라고 규칙을 만들어서 풀었고, 틀렸다.
이 문제에서 지켜야하는 규칙은 단 하나, 내가 이 숫자를 불렀을 때, 상대가 필승 칸을 먹으면 내가 진다. 그 외엔 내가 이긴다.이다. 다르게 표현해보면, 내가 숫자를 불렀을 때, 상대가 패배 칸(필승이 아닌 칸)이나 막힌 칸만 부를 수 있다면, 내가 이긴다.다.
이 규칙을 먼저 찾고, 규칙에 맞게 코딩해야 한다. 이는 귀납적 추론이 아닌, 연역적 추론이며, 문제에서 찾아낼 수 있는 부분이다.
코딩 테스트를 풀 때, 유저의 가장 큰 적은 반례다. 어디서 반례가 튀어나올지 모른다. 반례를 잘 회피해서 지나가려면, 반례를 찾을 때마다 그때그때 땜빵하는 게 아니라, 명확한 규칙을 바탕으로 코드를 설계해야 한다. 그 규칙의 결과로, 모든 반례가 사라져야 올바른 코드가 된다. 앞으로 문제를 풀 땐, 이점을 유념하고 풀어보자. 앞으론, 사례를 먼저 생각하는 대신, 문제에서 주어진 규칙을 먼저 찾아내고, 그것대로만 푸는 연습을 해보자. 그래야 내 실력이, 근본적인 부분부터 향상될 것 같다.
강평
솔직히, 어려웠다. 말귀 못 알아먹는 Gemini 때문에 화도 조금 났다. 그래도, 내가 문제를 풂에 있어 무엇이 문제인지는, 확실하게 느꼈다.
그리고, 좀 더 솔직히 얘기하자면 재밌었다. 내가 좋아하는 웹툰 중, 네이버 웹툰의 '킬 더 킹'이라는 웹툰이 있는데, 게임 이론은 마치 그 웹툰에 나오는 결함 게임과도 같았다.
결함 게임이란, 의도적으로 게임에 결함을 숨겨, 결함을 찾아낸 사람은 무조건 승리하는 게임을 일컫는다. 게임 이론 역시, 결함이 존재한다. Nim Game, 여기서의 베스킨라빈스 게임은 필드에 필승칸이 존재하고, 그걸 선점한 사람은 최선의 수를 두면 반드시 이긴다.는 특징이 있지 않나. 결함을 찾는 건 성공했는데, 좀 다르게 찾아서 문제지... (오히려 베라 게임을 너무 잘 알아서 문제였을 수도)
평소에도 이런 두뇌 퀴즈류는 참 좋아했는데, 막상 골드부터 마주치니 상당히 어지럽고(물리적) 힘들었다. DP 골드인 줄 알았더니, 냅다 처음 보는 게임 이론 골드를 만나서....... 그래도 이제, 이렇게 힘들게 지식을 얻었으니, 몇 문제 더 풀어서 내 것으로 완전히 만들어야지.
오늘도 알고리즘 문제에 거진 8시간은 쓴 것 같다. 1시에 캡스톤디자인 회의를 시작해서 4시 30분에 끝내고, 저녁을 먹은 후 계속 문제를 풀었는데도 벌써 시간이 새벽 1시다. 푸는 것보다, 풀이를 보고, 이해할 때까지 물어뜯고, 재해석하고, 다르게 생각해보는 게 진짜 오래 걸렸고, 그덕에 슬슬 두통이 심해진다. 이제 프로젝트도 3개로 늘어났으니, 이렇게 알고리즘에만 몰두하면 안 될 텐데.... 내일부턴 진짜, 진짜 빨리 풀고 할 일을 해야지.
마지막으로, 킬 더 킹 미리보기 빨리 올라오면 좋겠다. 하필 왜 거기서 끊겨서 진짜 쿠키가 있어도 볼 수가 없고 원작 찾아 인터넷을 파내고 다녀도 1부가 끝이고 그래서 어떻게 된 건데 빨리 올려줘 제발
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준/Python3] 12015번. 가장 긴 증가하는 부분 수열 2 - 가장 쉬운 원리 이해 (0) | 2026.02.13 |
|---|---|
| [백준/Python3] 14238번. 출근 기록 (0) | 2026.02.08 |
| [백준/Python3] 1105번. 팔 (0) | 2026.02.06 |
| [백준/Python3] 1024번. 수열의 합 (0) | 2026.02.02 |
| [백준/Python3] 1018번. 체스판 다시 칠하기 (0) | 2026.01.31 |