[BAEKJOON] 1654번 랜선 자르기

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

문제조건

1. 랜선의 개수 K, 그리고 필요한 랜선의 개수 N개를 만들 수 있는 랜선의 최대 길이를 구하라.
2. K개를 잘라서 모두 N개의 같은 길이의 랜선으로 만든다.

접근방법

 

조건에 따른 참, 거짓이 두구간으로 명확히 나뉘므로, 매개변수 탐색이 떠올랐다.

다만 너무 만만하게 보고 들어간건지 진짜 많이 틀렸다,,,

부끄럽습니다,,,

틀린원인

 

질문 게시판을 찿아 보면서 여러가지 반례들을 보고 다른 사람들의 이유는 무엇인지 계속해서 찾아봤다.

1. left 값 설정
2. long long형으로 선언
3. right 값 설정

사실 이 모든게 문제에서 주어진 정수 범위에 있었다. 

랜선의 길이는 2^31-1보다 작거나 같은 자연수  라는 부분에서 각각 계산을 하다보면 한번만 덧셈이 잘못되어도 int 형에서는 32비트 정수값보다 큰 값으로 오버플로우가 될수 있기 때문에 long long 형으로 자료형을 설정해야한다. 그리고 left 를 0으로 설정할 경우 zeroDivision이 나올수 있는 반례도 존재한다. 또한 나는 처음에 right값을 등장하는 모든 수의 합으로 설정해줬는데, 최악의 경우 n 값도 매우 큰 수이기 때문에 n번을 돌면서 시간 초과가 발생하기 때문에 strict하게 잡아주는 것이 중요하다.

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

long long k, n, arr[10001];

bool judge(int mid){
	long long cnt = 0;
	for(int i = 0; i < k; i++)
		cnt += (arr[i] / mid);
	return cnt >= n;
}

int main() {
	cin >> k >> n;
	long long left = 1, right = 0;
	for(int i = 0; i < k; i++){
		cin >> arr[i];
		right = max(right, arr[i]);
	}
	right += 1;
	while(left + 1 < right){
		long long mid = (left+right) / 2;
		if(judge(mid)) left = mid;
		else right = mid;
	}
	cout << left;
}

삽질 결과,,,