Python에서 n번의 복사·붙여넣기 연산으로 출력할 수 있는 최대 문자 수 구하기

문제 개요

숫자 n이 주어졌을 때, 아래 세 가지 연산을 정확히 n번 수행하여 화면에 나타낼 수 있는 최대 문자 개수를 구하는 것이 목표입니다.

• 문자 'x' 하나를 삽입한다.
• 화면에 있는 모든 문자를 복사한다.
• 복사해 둔 내용을 붙여넣는다.

예를 들어 n = 12가 입력으로 주어지면, 정답은 81입니다.

풀이 전략

이 문제는 n의 크기에 따라 두 가지 경우로 나누어 해결할 수 있습니다.

1. n이 4 이하인 경우

복사와 붙여넣기를 활용하려면 최소 2회 이상의 연산이 추가로 소모됩니다. 따라서 연산 횟수가 짧을 때는 매번 새로운 문자를 삽입하는 것이 항상 유리하므로, 그대로 n을 반환하면 됩니다.

2. n이 5 이상인 경우

처음 3번의 연산으로 'xxx'(3글자)를 만들고, 네 번째에 전체 복사, 다섯 번째에 붙여넣기를 수행하면 총 5번의 연산으로 6글자를 확보할 수 있습니다. 이후에는 남은 연산마다 문자 수(v)를 일정한 패턴으로 늘려가며 최댓값을 추적합니다.

알고리즘에서 사용하는 변수는 다음과 같습니다.

• v = 6: 현재까지 확보한 문자 수
• x = 3: 한 번의 연산으로 증가하는 문자 수
• i = 5: 지금까지 사용한 연산 횟수
• j = 0: 증가 패턴을 제어하는 카운터

i가 n에 도달할 때까지 아래 과정을 반복합니다.

• v에 x를 더하고, i와 j를 각각 1씩 증가시킨다.
• j가 3의 배수이면 x를 1.5배(int(x * 1.5))로 만든다.
• j를 3으로 나눈 나머지가 1이면 x를 그대로 유지한다.
• 그 외의 경우(나머지가 2)에는 x를 두 배로 만든다.

반복이 종료되는 시점의 v가 곧 구하고자 하는 최대 문자 수입니다.

파이썬 구현 코드

class Solution:
    def solve(self, n):
        # n이 4 이하이면 삽입만 반복하는 것이 최선
        if n <= 4:
            return n

        v = 6   # 현재 문자 수
        x = 3   # 연산당 증가량
        i = 5   # 사용한 연산 수
        j = 0   # 증가 패턴 카운터

        while i != n:
            v += x
            i += 1
            j += 1

            if j % 3 == 0:
                x = int(x * 1.5)
            elif j % 3 == 1:
                pass      # 증가량 유지
            else:
                x *= 2    # 증가량 두 배

        return v

ob = Solution()
n = 12
print(ob.solve(n))

입력 및 실행 결과

입력:

12

출력:

81

n = 12일 때 동작 과정

위 표에서 확인할 수 있듯이, 12번의 연산을 모두 사용한 시점에 문자 수가 81에 도달하며 이것이 n = 12에서 만들 수 있는 최댓값입니다.

정리

이 알고리즘은 연산 횟수가 적을 때는 단순 삽입이, 충분히 많을 때는 '전체 복사 후 반복 붙여넣기'가 유리하다는 직관에 기반합니다. 반복문이 n에 도달할 때까지 한 번씩만 실행되므로 시간 복잡도는 O(n), 추가 메모리는 O(1)로 매우 효율적으로 동작합니다.