백준 1259 랜선 자르기 c++ [컴공과고씨]

알고리즘/백준

시간빌게이츠 2022. 3. 11. 19:20

1259번: 팰린드롬수

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다.

www.acmicpc.net

처음 생각했던 방법은 전부 랜선을 합쳐서 k개의 랜선으로 나눈 후 나온 값을 이용해 각 랜선의 길이 만큼 비교하여 조건에 맞을 때까지 1씩 줄여가는 방법을 써보았지만 당연히 시간초과에 걸렸다.

그래서 시간을 줄이기 위해 이분 탐색을 이용하여 반 씩 나누어 가며 잘라야할 길이를 찾음.

사용 알고리즘 : 이분탐색

yea!