Greedy 접근법 - 백준 16206번

위 문제에 대한 알고리즘은 다음과 같다.

1) 10으로 나누어 떨어지는 케이크부터, 그 중에서도 작은 순으로 커팅을 진행해야한다. (10은 커팅제외)

ex) 20이면 1번만 잘라도 2개가 바로 생기는데 50도 나눠떨어지긴 하지만 4번을 잘라야 5개가 생기므로 작은것부터 접근해주어야함. 

2) 10으로 나누어떨어지는 케잌들을 다 자르고도 횟수가 남으면 나누어떨어지지 않는 애들도 순차적으로 잘라준다. 

처음에는 이런식으로 코드를 짜려고 접근했었다. 이 알고리즘에서 내가 놓쳤던 부분은 다음과 같다.

1) 길이가 10보다 긴 애들로만 크게 그룹지어서 고려해줄 것이 아니라, 그 중에서도(10보다 길이가 길면서도) 10으로 나누어 떨어지고, 그중에서도 길이가 작은 애들부터 잘라주어야 길이가 10인 롤케이크 개수의 최대값을 구할 수 있다는 것.

2) 10으로 나누어떨어지는 애들은 칼질을 했을때 롤케이크가 한 개 더 생긴다는 것

이 중에서도 핵심이 되는 1번을 빼먹었더니 코드가 많이 꼬여서 아예 다시 알고리즘을 설정해서 접근했다. 

 

제대로 작성한 코드는 다음과 같다. 

 

import java.util.Arrays;
import java.util.Scanner;
 
public class rolecake {
    static Scanner scanner = new Scanner(System.in);
    static int num_rolecake = scanner.nextInt(); // 롤케이크 개수
    static int num_cutting = scanner.nextInt(); // 최대 자를 수 있는 횟수
    static int count = 0; //길이가 10인 롤케이크 개수
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        int len_rolecake[] = new int[num_rolecake];//롤케이크 길이를 저장할 배열
        int rest[] = new int[num_rolecake];//10으로 나눠떨어지지 않는 롤케이크의 길이를 임시로 저장해둘 배열
        int index=0;
        for(int i =0; i<num_rolecake; i++) { //롤케이크 길이를 입력받는다.
            len_rolecake[i]=scanner.nextInt();
        }
        
        Arrays.sort(len_rolecake); //10으로 나눠떨어지는것들 중 작은 길이의 것부터 잘라주는 것이 이득이므로 정렬해준다. 
        
        
        for(int i=0;i<num_rolecake;i++) {
            if(len_rolecake[i]==10)count++; //롤케잌 자체의 길이가 10이면, 자르지 않고 개수만 +1
            
            if(len_rolecake[i]>10) {
                if(len_rolecake[i]%10==0)cut(len_rolecake[i]); //롤케잌 길이가 10으로 나눠떨어지는것들에 대해 먼저 자르기 시작
                else rest[index++] = len_rolecake[i]; // 10으로 나눠떨어지지 않는 것들은 배열에 저장해두었다가 커팅횟수가 남으면 그때 자르기
                
            }
            
        }
        
        if(num_cutting>0) { //10으로 나눠떨어지는 롤케잌들을 다 자르고도 커팅횟수가 남았으면 
            for(int j=0; j<index; j++) cut(rest[j]); //나머지에 대해서도 커팅을 진행해준다. 
        }
        
        System.out.println(count);
        
        
 
    }
    public static void cut(int len){
        if(num_cutting<=0) return; // 최대커팅횟수를 넘지 않게 자를 수 있다. 
        else {count++;
            num_cutting--;
            int length = len-10; // 한번 자르고 남은 롤케잌의 길이
            if(length>10) {
                cut(length); // 남은 롤케잌의 길이가 10보다 길다면 재귀함수를 이용해서 다시 cut 함수를 실행해준다. 
            }
            else {
                if(length ==10) count++; //마지막 남은 조각의 길이가 10이라면 길이가10인 롤케잌 개수 +1을 해줌. 
                return;
            }
        
        }
        
        
    }
 
}
 

자바에서 전역변수를 활용할 때는 'static'을 활용한다. - 두 함수에서 변수의 값 공유가능

cf) 상수 선언시에는 'final'활용