[백준] 31926 밤양갱

문제

민우는 비비의 신곡 <밤양갱>에 꽂혀 하루 종일 "달디달고 달디달고 달디달고... 달디단"이 머릿속을 맴돌고 있다.

민우의 머릿속에선 daldidalgo가 총 $N$번 반복된 후, 반복이 완료되었다면 daldidan으로 끝나게 된다. 예를 들어 $N=3$이라면 민우의 머릿속엔 daldidalgodaldidalgodaldidalgodaldidan이 재생된다.

민우는 $N$이 주어지면 얼마나 빨리 daldidalgodaldidalgo...daldidan을 컴퓨터에 입력할 수 있는지 궁금하다. 매초 민우는 두 개의 작업 중 하나를 선택하여 시행할 수 있다.

알파벳 소문자 a부터 z 중에서 민우가 원하는 알파벳을 하나 골라서 지금까지 입력한 내용의 맨 뒤에 입력한다.
지금까지 입력한 문자열의 연속된 부분 문자열을 복사 후 입력한 내용의 맨 뒤에 붙여넣는다. 예를 들어 지금까지 작성한 문자열이 ajouapcshake라면, ajouapcshake를 복사할 수도, apc를 복사할 수도 있지만, aashake를 복사하여 붙여넣을 수는 없다.
민우는 몇 초 만에 머릿속에 떠오른 가사를 컴퓨터에 입력할 수 있을까?

입력

첫 번째 줄에 민우의 머릿속에 떠오른 daldidalgo의 횟수 $N$이 주어진다. $(1\leq N \leq 10^9)$ 

출력

민우가 문제에 언급된 시행 중 하나를 선택하여 매초 시행했을 때, $N$번의 daldidalgo를 입력한 후 $1$번의 daldidan을 입력할 수 있는 최소 시간을 출력한다.

내 풀이

n = int(input())

def bamyanggang(n):
    time = 10+(n-1)
    return time

print(bamyanggang(n))

예제 입력 1 N = 2의 경우를 생각하면
1) daldi → 5초
2) dal → 1초 (앞의 문자열에서 dal 복사)
3) go → 2초
4) daldidalgo → 1초 (앞 문자열 전부 복사)
여기까지 daldidalgo 2번 반복했으니 이제 daldidan 만 입력하면 됨
5) daldida → 1초 (앞 문자열에서 daldida 복사)
6) n → 1초
이렇게 11초가 걸린다고 파악했다.
이 때 1), 2), 3), 5), 6)은 문제의 조건을 만족하기 위해 항상 들어가는 똑같은 프로세스이고, 4)만이 여러 번 반복되게 되므로 1), 2), 3), 5), 6)의 기본 10초 + (반복 횟수 - 1초)가 정답이라고 생각해서 풀었는데 틀렸다.

다른 풀이를 보고 잘못을 깨닫고 다시 푼 코드는 아래와 같다. (설명은 코멘트)

n = int(input())

def bamyanggang(n):
    if n == 1:
        return 10
    else:
        repeat = 1
        cnt = 0
        while repeat < n+1:
            cnt += 1
            repeat *= 2
        return cnt + 9     # first daldidalgo (8) + final n (1)

print(bamyanggang(n))

코멘트

인지도가 전혀 없는 문제인지 ChatGPT나 Claude에 물어봐도 엉뚱한 대답만 내놓고 구글링해도 이 문제를 푼 사람도 거의 없고 풀었어도 파이썬으로 풀지 않아서 뭐가 잘못되었는지 어떻게 풀어야할지 감을 못 잡겠다. 다만 유형을 확인해보니 그리디라고 하는데, 이 유형이 대체 어딜 봐서 그리디인지 모르겠다. 내일 다른 사람들 TIL 살펴보면서 연구해봐야겠다.

다른 분들 풀이를 살펴보니 내가 이 문제를 잘못 파악하고 있다는 것을 깨달았다. N이 큰 숫자이면, daldidalgo만을 복사하는 것은 비효율적이다. N=5만 하더라도,
1) daldidalgo → 8초
2) daldidalgo daldidalgo → 9초 (앞에서 daldidalgo 복사)
3) daldidalgo daldidalgo daldidalgo daldidalgo → 10초 (앞에서 daldidalgo daldidalgo 복사)
4) daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldida → 11초 (앞에서 daldidalgo daldida 복사)
5) daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidan → 12초 (n 입력)
와 같이 앞에서 더 길어진 문자열을 복사해와서 더 짧은 시간에 입력을 할 수 있는 것이다.
이렇게 $2^n$ 로 복사할 수 있다는 것을 캐치하면 정답에 가까워진다.

References

https://www.acmicpc.net/problem/31926
https://kaydaela.tistory.com/147