Today's keyword : 그리디
📌 문제설명
https://www.acmicpc.net/problem/31926
📌 문제풀이
최소한의 입력 작업으로 주어진 패턴을 빠르게 완성하는 방법을 찾기 위해 반복되는 daldidalgo 패턴을 어떻게 효율적으로 복사-붙여넣기 할 것인지 고민해야 합니다.
- 접근 방식
- daldidalgo를 반복하여 작성하고 마지막에 daldidan을 추가하는 작업이 요구됩니다.
- 하나씩 문자를 입력하는 방식이 아니라, 복사-붙여넣기 연산을 최대한 활용하여 패턴을 빠르게 완성하는 것이 목표입니다.
- 기본 패턴 (daldidalgo) 작성 시간
- daldi 까지 5초, dal 복사 + 1, go 알파벳 문자열 추가 +2초 = 8초로, 첫 번째 daldidalgo를 작성하는 데 8초가 필요합니다.
- 2의 제곱 배수 패턴을 활용
- 문제에서 반복 횟수를 복사-붙여넣기로 빠르게 증가시킬 수 있는데, 이를 위해 2의 제곱 배수로 복사해가며 빠르게 패턴을 늘려가는 것이 최적의 방법입니다.
- 예를 들어 2^1, 2^2, 2^3 등을 활용하여 최대한 목표 문자열에 근접하게 패턴을 완성해 나갑니다.
import sys
input = sys.stdin.readline
count = 8
N = int(input())
i = 1
while True:
if N - (2**i) == 0:
count = count + i + 2
break
elif N - (2**i) < 0:
count = count + i + 1
break
i += 1
print(count)
- 초기화: count를 8로 설정합니다. 이는 daldidalgo 패턴을 처음 작성하는 데 필요한 8초를 나타냅니다.
- 복사-붙여넣기 횟수 계산:
- 2**i 패턴을 통해 복사-붙여넣기로 패턴을 늘려가면서, 입력받은 N을 만들 수 있는 최소 연산 횟수를 찾습니다.
- 반복 종료 조건:
- 만약 N - (2**i) == 0이라면, 정확히 2**i만큼 반복된 것이므로, count에 i + 2를 추가하여 전체 시간을 계산하고 종료합니다.
- N - (2**i) < 0이면, 반복 횟수 N에 도달하지 못했으므로, 현재까지 수행한 복사 연산에 하나씩 추가하는 연산을 통해 남은 패턴을 완성합니다. 이 경우 count에 i + 1을 더해 최종 시간을 구하고 종료합니다.
예를 들어 N=3 인 경우:
- 첫 번째 daldidalgo를 작성하는 데 8초가 필요하므로 count = 8입니다.
- 2^1 = 2이므로, 복사-붙여넣기를 한 번 수행하면 count = 9가 됩니다.
- daldidalgo + daldidalgo (복사) : 8초 + 1초 (복사)
- N = 3에 도달하기 위해, 1을 추가하여 반복 횟수를 3으로 만들면 되므로 count에 1 + 1 = 2를 추가하여, 최종 count = 8 + 2 = 10이 됩니다.
- daldidalgo + daldidalgo (복사) + daldidalgodaldida (복사)
📌 오늘의 회고
이번 문제는 문제 이해하는거랑 풀기 어려웠다...
#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL