자바/C++ 백준 2805번 문제 : 나무 자르기

문제 출처 : https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

문제 :

 

풀이 :

Parametric Search 알고리즘으로 간단히 해결되는 문제인데 왜 정답률이 25% 밖에 안되는걸까

생각하며 문제를 제출하였지만 틀려버렸다.

문제를 다시보니 자료형의 범위를 초과해서 발생한 문제였다.

자료형의 범위를 잘 생각하자는 교훈을 얻게 되었다.

 

자바 소스코드 :

import java.util.*;
public class Main
{
    public long sumFunc(int[] arr, long mid) {
        long sum = 0;
        for(int x : arr) {
            if (x - mid > 0) sum += (x - mid);
            else sum += 0;
        }
        return sum;
    }
    
    public long solution(int n, int m, int[] arr) {
        long answer = 0;
        long lt = 0, rt = Arrays.stream(arr).max().getAsInt();
        while (lt <= rt) {
            long mid = (lt + rt) / 2;
            if (sumFunc(arr, mid) >= m) {
                lt = mid + 1;
                answer = mid;
            }
            else rt = mid - 1;
        }
        return answer;
    }
    
	public static void main(String[] args) {
	    Main T = new Main();
	    Scanner sc = new Scanner(System.in);
	    int n = sc.nextInt();
	    int m = sc.nextInt();
	    int[] arr = new int[n];
	    for(int i=0; i<n; i++) {
	        arr[i] = sc.nextInt();
	    }
		System.out.println(T.solution(n, m, arr));
	}
}

 

 

참고로 버퍼를 사용한 빠른 입출력을 사용하면 더 빠른 속도로 작동된다.

 

 

C++ 소스코드 :

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> v;
int n, m;

long long sumFunc(long long mid) {
    long long sum = 0;
    for(int x : v) {
        if (x - mid > 0) sum += (x - mid);
        else sum += 0;
    }
    return sum;
}

long long solution() {
    long long answer = 0;
    long long lt = 0, rt = *max_element(v.begin(), v.end());
    while (lt <= rt) {
        long long mid = (lt + rt) / 2;
        if (sumFunc(mid) >= m) {
            lt = mid + 1;
            answer = mid;
        }
        else rt = mid - 1;
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    v.resize(n);
    for(int i=0; i<n; i++) {
        cin >> v[i];
    }
    cout << solution();
    
    return 0;
}

 

정말 오랜만에 C++을 사용해 코드를 작성해보았다.

같은 코드인데 확실히 C++이 빠르다는걸 확인했다.

 

다음부터 자바 Scanner 그만쓰고 빠른 입출력 사용해야 할 것 같다..