99클럽 코테 스터디 17일차 TIL + 반복

백준 31962번 밤양갱

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	1024 MB	1048	368	308	36.450%

문제

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

<장기하, 밤양갱, 2024>

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

민우의 머릿속에선 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을 입력할 수 있는 최소 시간을 출력한다.

---

문제 해석하기

문제를 해석하는데 조금 오래걸렸다. 문해력이 딸리는건가..?

이 문제는 "daldidalgo"라는 구절을 N번 반복하고 마지막에 "daldidan"을 붙여서 컴퓨터에 입력하는 데 필요한 최소 시간을 구하는 문제이다. 여기서 민우가 매 초마다 할 수 있는 작업은 다>음 두 가지이다.

1. 알파벳 소문자를 하나씩 직접 입력하기 (1초 소요)
2. 이미 입력한 문자열의 일부를 복사해서 붙여넣기 (1초 소요)

• 첫 번째 "daldidalgo"를 만들기 위한 시간
  • "daldidalgo"는 10글자이므로 일반적으로 10초가 걸릴 수 있지만, 복사-붙여넣기를 사용하여 시간을 줄일 수 있다.
  • 이 문제에서 "daldidalgo"를 만들 때 복사-붙여넣기를 사용하여 8초에 완료할 수 있도록 설정한다.
• 복사-붙여넣기를 통한 반복
  • 이후에는 이미 만들어진 "daldidalgo"를 복사해서 붙여넣기 방식으로 구절을 효율적으로 반복할 수 있습니다.
  • 매번 daldidalgo 구절의 개수를 2배로 늘려가며 N에 도달할 때까지 복사-붙여넣기를 한다.
• 최종 "daldidan" 추가
  • 마지막 "daldidan"을 추가할 때는, 이미 입력된 "daldida"까지를 복사하고 마지막 "n"만 입력하는 방식으로 해결한다. 이는 총 2초가 걸린다.

---

=> 코드를 두개 작성해봤다. 하나는 생각한 대로 계산될 수 있도록 했고, 아래의 코드는 최적화를 시켜서 코드를 최대한 짧고 간결하게 작성할 수 있도록 하였다.

# 코드1

import sys
input = sys.stdin.read

def min_time(n):
    time = 8  # "daldidalgo"를 효율적으로 입력하는데 8초

    # 복사 가능한 "daldidalgo"의 개수를 구하기 위해 변수 설정
    count = 1  # 현재까지 만든 "daldidalgo" 개수
    steps = 0  # 복사-붙여넣기 작업 횟수

    # 2배씩 복사-붙여넣기를 해서 목표인 n에 도달하거나 넘어갈 때까지 반복
    while count < n:
        count *= 2  # "daldidalgo" 개수를 2배로 늘림
        steps += 1  # 복사-붙여넣기 작업을 1회 수행함

    time += steps  # 복사-붙여넣기 작업에 걸리는 시간 추가
    if count == n:
        time += 2  # "daldidan"을 붙이는 데 2초가 걸림
    else:
        time += 1  # 남은 부분을 타이핑하고 "daldidan"을 붙이는 데 1초 추가

    return time

# 입력과 출력
n = int(input().strip())
print(min_time(n))

---

# 코드2

import sys
input = sys.stdin.read

def min_time(n):
    count = 8  # 첫 번째 "daldidalgo" 생성 시간
    i = 1

    # n에 가장 가까운 2의 제곱수를 찾는 반복문
    while 2 ** i < n:
        i += 1
    
    # 필요한 복사 횟수와 마지막 "daldidan" 추가 시간 계산
    count += i + (2 if 2 ** i == n else 1)
    
    return count

# 입력 및 결과 출력
n = int(input().strip())
print(min_time(n))

---

오늘의 회고

처음에는 "daldidalgo"를 완전히 직접 입력해야 한다고 생각해 10초로 계산하는 실수를 했다. 하지만, 반복되는 부분 문자열을 복사-붙여넣기 방식으로 효율적으로 입력하는 방법을 떠올리면서, 초기 입력 시간을 8초로 줄일 수 있었다.

이 과정에서 복사-붙여넣기를 활용해 시간을 최적화하는 사고 방식을 익힐 수 있었고, 문제 해결 능력 또한 한층 성장하는 경험이었다. 앞으로도 미처 고려하지 못했던 부분들을 해결해나가며 더 나은 코드를 작성할 수 있을 것 같아 뿌듯하다.