[백준/Python] 2885 초콜릿 식사(그리디)

BOJ

그리디 2885 초콜릿 식사

문제로 이동!

문제

학교 근처 편의점에 새 초콜릿이 들어왔다. 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다. 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다. 즉, 1, 2, 4, 8, 16, …개의 정사각형으로 이루어져 있다.

상근이는 점심식사로 초콜릿을 먹는다. 이때, 적어도 K개 정사각형을 먹어야 남은 수업을 졸지 않고 버틸 수 있다. 상근이의 친구 선영이도 초콜릿을 좋아한다. 선영이는 초콜릿은 돈을 주고 사기 아깝다고 생각하기 때문에, 상근이가 주는 초콜릿만 먹는다.

상근이는 막대 초콜릿를 하나 산 다음에, 정확하게 K개 정사각형이 되도록 초콜릿을 쪼갠다. K개는 자신이 먹고 남는 것은 선영이에게 준다.

막대 초콜릿은 나누기 조금 어렵게 되어 있어서, 항상 가운데로만 쪼개진다. 즉, 정사각형이 D개 있는 막대는 D/2개 막대 두 조각으로 쪼개진다.

K개 정사각형을 만들기 위해서, 최소 몇 번 초콜릿을 쪼개야 하는지와 사야하는 가장 작은 초콜릿의 크기를 구하는 프로그램을 작성하시오. 상근이는 초콜릿을 하나만 살 수 있다. 꼭 한 조각이 K개일 필요는 없고, 여러 조각에 있는 정사각형을 합쳤을 때 K개이면 된다.

입력

첫째 줄에 K가 주어진다. (1 ≤ K ≤ 1,000,000)

예제 입력

    """
    입력
    6
    출력
    2
    """

풀이

문제를 이해하기가 조금 어려웠는데, 2의 제곱 형태인 초콜릿을 계속 반씩 나눈 값을 더해서 입력값인 k가 되게 만들면 되는 최소값을 구하면 된다. 우선 이 문제는 더할 수 있는 값이 2의 제곱수들이기 때문에 k값이 어떤 2의 제곱수끼리 더해졌는지를 알아내야 한다. 그렇기 때문에 2의 제곱수중 가장 큰 수부터 나누어서 나머지가 0으로 떨어지면 나눈 값까지만 초콜릿을 반씩 쪼개면 된다. 만약 k가 홀수라면 초콜릿을 1개 까지 나눠야하기 때문에 계산을 적게하기 위해 얼리리턴 해준다.

solution

1. 우선 k값보다 큰 2의 제곱수가 무엇인지 반복문을 통해 찾아낸다.
2. 2의 제곱수로 상근이가 사야할 초콜릿 크기를 구해준다.
3. 가장 큰 2의 제곱수로 k를 나누었을 때 0이면 나누지 않아도 되기 때문에 얼리 리턴 해준다.
4. 가장 큰 2의 제곱수로 k를 나누었을 때 1이면 마지막 까지 나눠야 하기 때문에 2의 제곱수로 리턴 해준다.
5. 가장 큰 2의 제곱수부터 내림차순으로 k값을 나누어준다.
6. 2의 제곱수로 나누어지면 (최대 제곱수 - 해당 2의 제곱수)로 리턴해준다.

코드

    def solution(k):
        degree = 0
        while True:
            if 2**degree >= k:
                break
            degree += 1
    
        size = 2**degree
        if k == size/2:
            return 1
        if k%2 == 1:
             return size, degree
        for s in reversed(range(degree+1)):
            if k%(2**s) == 0:
                return size, degree - s
    
    
    if __name__ == "__main__":
        k = int(input())
        m, n = solution(k)
        print(m, n)