[알고리즘 문제풀이] 백준 16206 롤케이크

어제 진짜 공부하기 싫어서 빈둥대다가 한 문제 겨우 풀고 기절했다 ..
포스팅도 미루고 미루다가 또 오늘 코테보고 아무것도 하기싫어서 외출해서 볼 일 보고 돌아와서 이제야 쓴다.. 🥲 ( 으에엥러ㅔ넘레러어) 그래도 스터디 덕에 꾸역꾸역 문제푸는 나 칭찬해.. 오늘의 문제는 코테봤으니 패스다..

그래서 오늘 포스팅 할 문제는 백준 16206 - 롤케이크이다. 풀기 싫어서 쉬운걸로 골라 풀었다..ㅎㅎㅎㅎㅎㅎㅎㅎ 실버 2 ..

오늘은 프로젝트 마무리 해야하고, 내일은 약속 있으니.. 월요일부터는 다시 열심히 달리기로 ! 🔥

문제

오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 길이가 10인 롤케이크를 최대한 많이 만들려고 한다.

롤케이크는 다음과 같은 과정을 통해서 자를 수 있다.

1. 자를 롤케이크를 하나 고른다. 길이가 1보다 큰 롤케이크만 자를 수 있다. 이때, 고른 롤케이크의 길이를 x라고 한다.
2. 0보다 크고, x보다 작은 자연수 y를 고른다.
3. 롤케이크를 잘라 길이가 y, x-y인 롤케이크 두 개로 만든다.

재현이는 롤케이크를 최대 M번 자를 수 있다. 이때, 만들 수 있는 길이가 10인 롤케이크 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 롤케이크의 개수 N과 자를 수 있는 최대 횟수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄에 롤케이크의 길이 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000)

출력

재현이가 만들 수 있는 길이가 10인 롤케이크 개수의 최댓값을 출력한다.

예제

입력1

3 1
10 10 10

출력1

3

입력2

3 1
10 10 20

출력2

4

입력3

3 3
20 20 20

출력3

6

입력4

5 7
10 20 30 40 50

출력4

11

입력5

5 8
34 45 56 12 23

출력5

8

풀이 방법

먼저 진짜 간단한 문제라고 생각했다가 두 번 제출 실패를 겪었다. 하지만 실패하고서 문제가 뭘까 고민하자마자 떠올릴 수 있었던 간단한 문제였다 ! 내가 겪은 과정에 도움이 되는 추천 예제를 아래에 적어두었다 ! 참고하면 좋을 듯 싶다 !

나의 추천 예제

3 1
30 30 20

3 1
18 19 20

먼저 위의 예제에서도 힌트를 줬듯이 이 문제는 같은 컷팅 횟수로 가장 많은 10 길이의 롤케이크를 얻는 것이 목표이다 ! 그러기 위해서는 먼저 판단해야하는 우선순위가 존재한다 !

1. 15와 20을 비교하면 1번의 컷팅으로 후자가 더 많은 길이 10의 롤케이크를 얻는다.
2. 30과 20을 비교하면 1번의 컷팅으로 후자가 더 많은 길이 10의 롤케이크를 얻는다.

위의 첫 예시에서 알 수 있듯이 10의 배수인 것들은 나머지가 또 10이 될 수 있기 때문에 10의 배수인 것들을 아닌 것들보다 먼저 판별해야한다. 그래서 나는 입력받을 시에 10의 배수인지 아닌지를 판별하여 다른 리스트에 넣어주었다.

또한 두 번째 예시에서 알 수 있듯이 10의 배수인 것들 중에서도 가능한 컷팅 횟수에 따라서 나머지가 10의 배수이긴 하지만 10이 아닐수도 있기 때문에 작은 것부터 판별해나가야 가장 많은 롤케이크를 얻을 수 있다 ! 그렇기 때문의 10의 배수인 롤케이크 리스트는 오름차순으로 정렬해준 후 판별을 시작했다.

위와 같은 알고리즘이기 때문에 알고리즘 분류를 오늘은 딱히 확인하지는 않았지만 아마도 그리디지 않을까 싶다 !

그렇다면 위의 우선순위로 이제 얻을 수 있는 롤케이크 수를 계산해 나가야한다. 이 과정은 10으로 나눈 몫을 이용해주었다. 이 과정에서 10의 배수이냐 아니냐, 그리고 컷팅횟수가 몇 개 남았느냐에 따라서 생기는 차이를 반영해주었다.

즉 각 롤케이크를 탐색하면서 아래의 과정을 수행한다.

1. 10의 배수인 경우
   • 모든 롤케이크 탐색이 완료되거나, 컷팅 가능 횟수가 0회 이하면 자를 수 없는 것이므로, 탐색을 중단한다.
   • 조각의 수는 케이크의 길이를 10으로 나눈 몫이다.
   • 마지막 조각은 앞을 자르고 남은 나머지이지만 길이가 10인 것이므로 컷팅 횟수는 조각보다 하나 작다.
   • 만일 위에서 계산한 컷팅 횟수가 가능한 컷팅 횟수보다 큰 경우에는 가능한 컷팅 수 만큼만 자를 수 있기 때문에 컷팅수를 가능한 컷팅 횟수로 업데이트 해준다.
   • 컷팅 횟수가 업데이트되면 조각의 수도 바뀌기 때문에 조각의 수도 변경된 컷팅 횟수로 업데이트 해준다.
   • 이 경우에 남은 조각의 길이가 10이면 조각을 하나 더 증가시켜주고, 10의 배수이지만 20, 30 ... 과 같이 10이 아니라면 증가시키지 않는다.
   • 컷팅 횟수만큼 가능 컷팅 횟수를 감소해주고, 최종 결과 조각의 수를 계산된 조각 수만큼 증가시켜준다.
2. 10의 배수가 아닌 경우
   -모든 롤케이크 탐색이 완료되거나, 컷팅 가능 횟수가 0회 이하면 자를 수 없는 것이므로, 탐색을 중단한다.
   • 조각의 수는 케이크의 길이를 10으로 나눈 몫이다.
   • 10의 배수가 아닌 조각이기 때문에 나머지는 10보다 작을 것이므로 컷팅 수는 조각 수와 같다.
   • 만일 위에서 계산한 컷팅 횟수가 가능한 컷팅 횟수보다 큰 경우에는 가능한 컷팅 수 만큼만 자를 수 있기 때문에 컷팅수를 가능한 컷팅 횟수로 업데이트 해준다.
   • 컷팅 횟수가 업데이트되면 조각의 수도 바뀌기 때문에 조각의 수도 변경된 컷팅 횟수로 업데이트 해준다.
   • 컷팅 횟수만큼 가능 컷팅 횟수를 감소해주고, 최종 결과 조각의 수를 계산된 조각 수만큼 증가시켜준다.

( 위의 과정에서 대부분의 과정은 두 경우가 동일하고, 볼드체로 표시한 부분만 다르게 처리해주면 된다 ! 나는 간단한 과정이라 따로 함수로 빼거나 하지 않고 그냥 동일 코드를 작성해주었다.. )
탐색이 종료된 시점의 최종 결과 조각의 수를 결과로 반환한다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // reader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // writer
        StringTokenizer st; // tokenizer

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int count = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> cakes1 = new ArrayList<>();
        ArrayList<Integer> cakes2 = new ArrayList<>();
        int temp;
        for(int i=0; i<n; i++){
            temp = Integer.parseInt(st.nextToken());
            if(temp % 10 == 0) cakes1.add(temp);
            else cakes2.add(temp);
        }
        int result = 0;
        int cut, piece;

        cakes1.sort(Comparator.naturalOrder());
        for(int cake: cakes1){
            if(count <= 0) break;

            piece = cake/10;
            cut = piece-1;

            if(count < cut){
                cut = count;
                piece = cut;
                if(cake - (piece*10) == 10) piece++;
            }
            count -= cut;
            result += piece;
        }

        for(int cake: cakes2){
            if(count <= 0) break;

            piece = cake/10;
            cut = piece;

            if(count < cut){
                cut = count;
                piece = cut;
            }
            count -= cut;
            result += piece;
        }

        bw.write(String.valueOf(result));

        bw.write( "\n"); // for return value
        bw.flush(); // flush
        bw.close(); // close
        br.close(); // close
    }
}