[백준 31926] 밤양갱

문제

달디달고, 달디달고, 달디단, 밤양갱, 밤양갱

<장기하, 밤양갱, 2024>

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

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

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

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

민우는 몇 초 만에 머릿속에 떠오른 가사를 컴퓨터에 입력할 수 있을까?

입력

첫 번째 줄에 민우의 머릿속에 떠오른 daldidalgo의 횟수 N이 주어진다. (1≤N≤109)

출력

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

---

풀이

N=1 인 경우

daldidalgo를 완성하려면 몇초가 걸릴까?

d
da
dal
dald
daldi
daldidal
daldidalg
daldidalgo

8초가 걸린다

 

N=1 보다 큰 경우

dadidalgo daldida n # N=1, 8+1+1
dadidalgo dadidalgo daldida n # N=2, 8+1+1+1
dadidalgo dadidalgo dadidalgodaldida n # N=3, 8+1+1+1
dadidalgo dadidalgo dadidalgodadidalgo daldida n # N=3, 8+1+1+1+1

 

daldidalgo를 하나 만드는데 8초, 이후에는 2의 제곱수만큼 복사가 가능하다

 

주의할 점은 마지막 daldidan 을 어떻게 처리하냐인데

나는 daldida를 하나의 daldidalgo로 인식하여 입력값을 N+1로 처리하였고 그 뒤에 n만 붙이는 방식으로 생각했다

# 밤양갱
import sys
input = sys.stdin.readline

N = int(input())
repeat = 1
cnt = 0

while repeat < N+1:
    cnt += 1
    repeat *= 2

if N==1:
    print(10)
else:
    print(8+cnt+1)