백준 - 롤케이크 ( 16206번, JAVA )

Greedy ( https://www.acmicpc.net/problem/16206 )

풀이

• 정렬까지 하고 while문 로직을 10번은 썼다가 지운듯 .. 그래서 다른 사람 풀이를 찾아봤다
• 내가 생각한건 나머지가 작은순으로 [길이,10으로 나눈 나머지] 정렬 후 자를 수 있는 횟수만큼 자르면서 카운팅
• 근데 이게 로직은 맞는데 생각한대로 구현이 안됐다 😂
• 보니까 10의 배수 길이인 케이크를 먼저 자른뒤 먼저 자른 10의 배수가 아닌 것들을 제외하고 잘라서 카운팅
• 다른 사람 풀이 보니까 우선순위큐 썼는데 어차피 정렬 재정의 해서 하는건 같으니 좀 더 머리 굴려서 풀자

package problem_solving.greedy;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class BaekJoon_16206 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		int [][] cakeList = new int [n][2];

		for(int i = 0 ; i < n ; i++) {
			int num = Integer.parseInt(sc.next());
			cakeList[i][0] = num;
			cakeList[i][1] = num % 10 ;
		}

		Arrays.sort(cakeList, new Comparator<int[]>() {
			@Override
			public int compare(int [] o1, int[] o2) {
				return o1[0]-o2[0]; 
			}
		});

		int index =0 ; 
		int answer = 0 ;

		while (index < n && m > 0) {
			int num = cakeList[index][0]; 
			int remainder = cakeList[index][1];
			index++;

			if (num < 10) continue; 

			int pieces = num / 10; 
			int cutsNeeded = pieces - 1; 

			if (remainder == 0) {
				if (m >= cutsNeeded) { 
					answer += pieces;
					m -= cutsNeeded;
				} else { 
					answer += m;
					m = 0;
				}
			}
		}

		index = 0;
		while (index < n && m > 0) {
			int num = cakeList[index][0];
			int remainder = cakeList[index][1];
			index++;

			if (num < 10 || remainder == 0) continue; 

			int pieces = num / 10;
			int cutsNeeded = pieces; 

			if (m >= cutsNeeded) { 
				answer += pieces;
				m -= cutsNeeded;
			} else {
				answer += m;
				m = 0;
			}
		}

		System.out.println(answer);
	}

}