[Java] 백준 2805 나무 자르기

2805 나무 자르기 문제 링크

#1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		
		long answer = 0L;
		long sum = 0L;
		int i;
		for(i=1; i<N; i++) {
			sum += (arr[N-i] - arr[N-i-1]) * i;
			if(sum >= M) break;
		}
		
		answer = arr[N-i-1]+((sum-M)/i);
		System.out.println(answer);
	}
}

• 배열 길이가 1인 경우를 생각해주지 않음

#2

package forStudy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_2805 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
        
		long answer = 0L;
		if(N==1) {
			answer = arr[0] - M;
		}
		else {
			long sum = 0L;
			int i;
			for(i=1; i<N; i++) {
				sum += (arr[N-i] - arr[N-i-1]) * i;
				if(sum >= M) break;
			}
			
			answer = arr[N-i-1]+((sum-M)/i);
		}
		
		System.out.println(answer);
	}
}

• 런타임 에러..? : 배열 범위를 벗어남..
• 이런 식으로 정말정말정말 많은,, 시행착오를 거쳤다..

#3

package week02;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_2805 {
	static int[] arr;
	static int N;
	static int M;
	
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);
        
        if(N==1) System.out.println(arr[0] - M);
        else System.out.println(findMax());
    }
    
    static long findMax() {
    	long sum = 0L;
        int i;
        for(i=1; i<N; i++) {
        	if(sum+(arr[N-i]-arr[N-i-1])*i < M) {
        		sum+= (arr[N-i]-arr[N-i-1])*i;
        	}
        	else return (M-sum)%i==0 ? arr[N-i]-(M-sum)/i : arr[N-i]-((M-sum)/i+1);
        }
        if((M-sum)%i==0) return arr[N-i]-(M-sum)/i;
        else return arr[N-i]-((M-sum)/i+1);
    }
}

• 아니 이게.. 아이디어를 떠올리는 건 얼마 안 걸렸는데
• (M-sum)%i==0 ? arr[N-i]-(M-sum)/i : arr[N-i]-((M-sum)/i+1)
• 이 로직을 구해내는 게 정말 오래 걸렸다..
• 그래도 성공...!