[백준 시리즈] 21756번 : 브론즈2 - 지우개 / Python

제목 : 지우개

출처 : 백준 /  21756번: 지우개 (acmicpc.net)

사용 자료구조&알고리즘 : 수학, 시뮬레이션

 

문제 설명

 

1. N (1<=N<=100) 개의 칸에 1부터 N까지 왼쪽부터 순서대로 저장되어 있다.

2. 다음 작업을 수가 정확히 하나가 남을 때까지 반복한다.

1. 홀수번 칸의 수들을 모두 지운다.
2. 남은 수들을 왼쪽으로 모은다.

3. 마지막으로 남은 수를 계산해라.

 

제한

시간 제한 : 1초

메모리 제한 : 512 MB

 

문제 풀이

1단계 : 최대 시간복잡도는 얼마인가?

N의 크기가 100 이하이기 때문에 시간 복잡도 제한이 없다.

 

2단계 : 핵심 아이디어는 무엇인가?

• 문제에서 제시된 기능들을 정직하게 구현하면 되는 문제이다.
• 홀수 또는 짝수번 칸의 수만 남으므로 각 숫자의 새로운 위치는 '현재 위치 / 2'이다.
• $log_2N$번만 실행하면 무조건 답이 나온다.

정답 코드

import math

n = int(input())
arr = [i for i in range(1, n+1)]

def remove():
    for i in range(n):
        if i % 2 == 0:
            arr[i] = 0

def shift():
    for i in range(1, n, 2):
        arr[i//2] = arr[i]

length = (int)(math.log(n, 2))
for i in range(length):
    remove()
    shift()

print(arr[0])