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

이분 탐색 문제.

이분 탐색 문제이고 실버3 문제임에도 고려해줄 사항이 생각보다 많아서 반례를 한번 찾아보고 풀었다.

 

처음 문제를 봤을 때

처음에는 우선순위 큐로 만들어서 긴 랜선들을 자르는 식으로 구현해보려고 했다.

그런데 문제 아래에 힌트를 보면

이렇게 나와있었고, 결국 우선순위 큐를 이용하는 그리디 방식의 풀이는 틀렸다는 것을 알게됐다.

 

랜선 자르기 같은 문제를 예전에 풀었던 적이 있었는데, 이분 탐색으로 풀었던 기억이 있어서 이분탐색으로 시도했고,

몇번 구상해보니 확실히 이분탐색이라는 것을 알게됐다.

 

문제 풀이

문제가 이분탐색이라는 것을 알게되면 그 뒤로는 간단하다.

나같은 경우는 vector 배열에 담고, algorithm STL에 있는 sort 메서드를 사용해서 정렬해 준 후에

1 ~ [입력받은 가장 큰 값]에서 이분탐색으로 찾는 방식으로 구현했다.

테스트 케이스인 802, 743, 457, 539를 살펴보자면 처음의 범위는 1 ~ 802이다.

front를 1, tail을 802라고 생각하면

이를 정렬해서 457, 539, 743, 802의 상태에서 살펴보자면

• 1 + 802 = 803 / 2 = 401, 401을 457, 539, 743, 802로 각각 나눈 값을 더하면 5가 된다. 5는 11보다 작으므로 front는 그대로 두고, tail을 middle - 1로 생각한다.
• 1 + 400 = 401 / 2 = 200, 200을 457, 539, 743, 802로 각각 나눈 값을 더하면 11이 된다. 11은 11보다 작거나 같으므로 일단 값을 저장하고 front를 middle + 1로 생각한다.
• ...

위 경우의 수를 front <= tail일 때까지 반복한다.

밑줄 친 부분을 고려하지 않아서, 정확히는 tail 부분에서 middle - 1을 해 주는 것을 고려하지 않아서 틀렸다.

이분 탐색에서 내가 지금 middle을 고려해주고 있다는 사실을 항상 기억해야 한다.

즉, middle을 다시 굳이 고려할 필요는 없다는 뜻이다.

(물론 이 부분은 이분탐색 문제마다 크게 다를 것 같긴 하지만 이 문제에서의 경우에는 그렇다.)

 

돌아와서 코드를 살펴보자면,

사용한 STL과 변수

vector, 그리고 sort메서드 사용을 위한 algorithm STL을 사용했다.

처음에 입력받는 num, need 변수가 있다.

그리고 result 변수가 있는데, 맨 처음에 1로 초기화를 시켜준다.

이중탐색을 하지 않을 수도 있는데, 결과값은 항상 1보다 크거나 같기 때문에 처음에 1로 초기화 해준다.

그리고 처음의 길이들을 담음 벡터 vec을 만들어준다.

 

메인함수 - 1

처음의 개수와, 필요한 개수를 입력받고, 개수마다 길이를 벡터에 저장한다.

그리고 오름차순으로 벡터를 정렬해준다.

메인함수 - 2

그리고 이분탐색을 해 준다.

맨 처음에 front를 1, tail을 벡터 배열에서 가장 큰 값, (나같은경우는 정렬했으므로 마지막 인덱스)

으로 초기화해준다.

그리고 front <= tail일때까지 while반복문을 돌면서 

내부에서 나눴을때의 총 합이 무엇인지에 따라 front와 tail을 바꿔준다.

경우는 위에서 고려한 사항들을 고려해주면 되므로 어렵지 않게 구현할 수 있는데, front나 tail이 무한루프에 빠지지 않거나, 값이 제대로 업데이트 되지 않거나 하는 경우만 조심해주면 된다.

 

 

반례는 아래 글에서 참고했다.

[테스트케이스 추가] 백준 1654번: 랜선 자르기 python, 파이썬

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인이 가능하다.