1. 오늘의 문제
오늘 문제는 좀 난해했다.
입력방식을 이해하기 어려워서 달디단을 n=1 부터 n=5까지 입력하고서야 규칙을 찾을 수 있었다.
내 머리에 한계인 것 같기도...
문제
달디달고, 달디달고, 달디단, 밤양갱, 밤양갱
<장기하, 밤양갱, 2024>
민우는 비비의 신곡 <밤양갱>에 꽂혀 하루 종일 "달디달고 달디달고 달디달고... 달디단"이 머릿속을 맴돌고 있다.
민우의 머릿속에선 daldidalgo가 총
N번 반복된 후, 반복이 완료되었다면 daldidan으로 끝나게 된다. 예를 들어
N=3이라면 민우의 머릿속엔 daldidalgodaldidalgodaldidalgodaldidan이 재생된다.
민우는
$N$이 주어지면 얼마나 빨리 daldidalgodaldidalgo...daldidan을 컴퓨터에 입력할 수 있는지 궁금하다. 매초 민우는 두 개의 작업 중 하나를 선택하여 시행할 수 있다.
알파벳 소문자 a부터 z 중에서 민우가 원하는 알파벳을 하나 골라서 지금까지 입력한 내용의 맨 뒤에 입력한다.
지금까지 입력한 문자열의 연속된 부분 문자열을 복사 후 입력한 내용의 맨 뒤에 붙여넣는다. 예를 들어 지금까지 작성한 문자열이 ajouapcshake라면, ajouapcshake를 복사할 수도, apc를 복사할 수도 있지만, aashake를 복사하여 붙여넣을 수는 없다.
민우는 몇 초 만에 머릿속에 떠오른 가사를 컴퓨터에 입력할 수 있을까?
2. 원리
핵심은 이어진 앞쪽의 단어에서 일부분만을 취하여 복사할 수 있다는 것이다.
이걸 이용해 n=1부터 쭉 적어보면 아래와 같다.
1번 입력
d a l d i (d a l) g o (dal3dida) n
1 2 3 4 5 6 7 8 9 10
2번 입력
d a l d i (d a l) g o (daldidalgo) (dal3dida) n
1 2 3 4 5 6 7 8 9 10 11
3번 입력
d a l d i (d a l) g o (daldidalgo) (daldidalgo daldida) n
1 2 3 4 5 6 7 8 9 10 11
4번 입력
d a l d i (d a l) g o (daldidalgo) (daldidalgo daldidalgo) (daldida) n
1 2 3 4 5 6 7 8 9 10 11 12
5번 입력
d a l d i (d a l) g o (daldidalgo) (daldidalgo daldidalgo) (daldidalgo daldida) n
1 2 3 4 5 6 7 8 9 10 11 12
결국 초기값은 10이고, n의 범위가 2의 n승 안쪽이라면 모두 같은 횟수값을 가지게 된다.
2의 N제곱이기에 숫자가 커도 이진탐색과 같은 시간 소요되므로 while문을 이용하면 된다.
구현은 간단하다.
3. 코드
a = int(input())
b = 1
total = 10
while True:
b *= 2
total += 1
if a < b:
total -= 1
break
if a == b:
break
print(total)
4. 느낀점
어렵지 않았으나 문제를 해석하기가 어려웠다.
나는 난독증인가...?
어쨌든 간단하지만 예제가 적어서 해석하기까지 시간이 조금 걸리는 문제였다.
