[백준] 1654번. 랜선 자르기 (C++)

문제 설명

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

 

해결 방법

너무 노가다로 풀었다..손으로 하다보면 규칙이 보인다..

케이스 하나를 손으로 다 풀어본 다음 그 특징을 코드로 옮겼다.

 

 

INPUT

K, N과 각각 랜선의 길이를 입력 받는다.

랜선의 길이는 입력 받으면서 동시에 최대값(max)을 확인했다.

 

EXCEPTION

예외 1)

K가 1인 경우.  result=랜선길이/N

이 케이스를 빼면 num=0인 경우 0으로 나눌 수 없는 경우 에러가 난다. 

예외 2)

max로 모든 랜선 길이가 나눠 진다면 result=max

이 케이스를 빼면 num을 높이고 확인하고자 할 때

first = resultCandidate[numIndex];
second = resultCandidate[numIndex - 1];

이 코드가 해당되지 않는다.

(아래 설명을 보면 더 이해가 될것)

 

CHECK

calculate cable num

num = 자를 랜선 길이를 num으로 설정

cableNum = num길이 만큼 랜선을 자를 때, 만들 수 있는 랜선 개수

check cable num

cableNum이 N이상이고 num+1도 확인한 경우면 result=num이고 끝난다.

cableNum이 N보다 작으면 num을 줄인다 (즉 cableNum을 늘린다.)

cableNum이 N보다 크거나 같으면 num을 높여가며 최대로 값이 큰 num을 찾아간다.

next

num과 resultCandidate를 갱신한다.

왼쪽 화살표 : num을 줄인다 / 오른쪽 화살표 : num을 늘린다

 

 

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


int main()
{
	//INPUT////////////////////////////////////
	int K, N;
	cin >> K >> N;

	vector<long long>length(K);
	
	int max = 0;
	for (int i = 0; i < length.size(); i++)
	{
		cin >> length[i];
		if (max < length[i]) { max = length[i]; }
	}
	


	//EXCEPTION////////////////////////////////
	//Exception 1
	if (K == 1) { std::cout << length[0] / N; return 0; }
	//Exception 2
	for (int i = 0; i < length.size(); i++) 
	{
		if (length[i] % max != 0) { break; }
		if (i==length.size()-1) 
		{
			std::cout << max; return 0;
		}
		
	}

	//CHECK/////////////////////////////////////
	long long num = max;
	long long numIndex = 0;
	vector<long long> resultCandidate = { num,0 };
	
	long long first, second;

	while (true)
	{
		//CALCULATE CABLE NUM ===================================================
		long long cableNum = 0; // 길이 num일때 만들 수 있는 랜선 개수는 cableNum
		for (int i = 0; i < length.size(); i++)
		{
			cableNum += (long long)(length[i] / num);
		}

		//CHECK CABLE NUM =======================================================
		if (cableNum >= N && abs(first - second) == 1)
		{
			//RESULT
			std::cout << num;
			break;
		}
		if (cableNum < N)
		{
			//num 을 줄이자
			first = resultCandidate[numIndex];
			second = resultCandidate[numIndex + 1];
			numIndex += 1;
		}
		else
		{
			//num을 높이자
			first = resultCandidate[numIndex];
			second = resultCandidate[numIndex - 1];
		}

		//NEXT===================================================================
		num = (first + second) / 2;
		resultCandidate.insert(resultCandidate.begin() + numIndex, num);
	}

	
}