2885.초콜릿 식사 - 백준온라인

in Dev. Log on Algorithms Solutions

백준 알고리즘 문제 풀이

해당 문제는 탐욕(greedy) 알고리즘을 사용하여 문제를 해결 했습니다.

링크 : image

2885.초콜릿 식사

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

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

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

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

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

입력(Input)

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

출력(Output)

첫째 줄에는 상근이가 구매해야하는 가장 작은 초콜릿의 크기와 최소 몇 번 쪼개야 하는지를 출력한다.

1. 문제 풀이

그리디 알고리즘을 이용하는 문제를 해결해보았다.

초콜릿이 나누어지는 경우가 무조건 D = D / 2로 반으로만 나눌 수 있고, 초콜릿의 크기는 2의 제곱 형태이다.

초콜릿을 반으로 나누면 나누어진 초콜릿 중 반 쪽은 그 상태로 남고, 다른 반 쪽으로 다시 나누기를 시도하여 이 초콜릿의 누적 개수가 K가 되면 되는 문제이다.

계속 나누다보면 결국에는 2 = 1 + 1이 될 것이니, 필요한 K의 갯수보다 한 제곱 더 큰 초콜릿을 사면 되는 것이다.

K = 6
\(2^2 = 4\) \(2^3 = 8\) 이므로 4 < K < 8
8의 초콜릿을 구매

위의 방식대로 초콜릿을 구매하고, 남은 개수는 다른 반쪽을 나누어가며 채워가면 된다.

8을 나누어 4개 | 4개
반쪽인 4개를 K에서 제외하고, 다른 반쪽을 나눈다.
K(6) - 4 = 2
4을 나누어 2개 | 2개
반쪽인 2개를 K에서 제외하면 정량이 된다.
K(2) - 2 = 0

이것을 코드로 표현하겠습니다.

import java.util.Scanner;

public class ChocolateEat_2885 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int D = 0;
        int i = 0;
        
        while(D < K) {
            D = (int)Math.pow(2, i);  // 1, 2, 4, 8, 16...
            i++;
        }

        int size = D, cnt = 0;
        while(K > 0) {
            if(K >= D) {
                K -= D;
            } else {
                D /= 2;
                cnt++;
            }
        }

        System.out.println(size + " " + cnt);
    }
}