[APS] 백준 3649. 로봇 프로젝트 C++ 풀이
Gold IV https://www.acmicpc.net/problem/3649
3649번: 로봇 프로젝트
문제 상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다. 구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다. 지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를
www.acmicpc.net
Problem
1. 구멍의 너비 x 센티미터(1 ≤ x ≤ 20, x는 정수)와 레고의 수 n(0 ≤ n ≤ 1000000), 레고 조각의 길이 ℓ이 주어진다. ℓ은 양의 정수이며, 단위는 나노미터이다. 레고 조각의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다. 레고 조각 중 구멍을 완벽하게 막을 수 있는 두 조각을 구한다.
2. 입력은 여러 개의 테스트 케이스로 이루어져 있다.
3. 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'을 출력하고, 막을 수 있는 경우에는 'yes ℓ1ℓ2'를 출력한다. (ℓ1≤ ℓ2) 정답이 여러 개인 경우에는 |ℓ1- ℓ2|가 가장 큰 것을 출력한다.
Solution
'입력은 여러 개의 테스트 케이스로 이루어져 있다.' 라는 문장을 간과한 덕분에 풀이가 맞는데 왜 자꾸 틀렸습니다! 가 나오나, 엄청 고민을 한 문제입니다. 예제 입력은 하나 밖에 주어지지 않았지만, 입력이 없을 때까지 입력을 계속 받아야 합니다. 아니 보통 이럴거면 예제 입력도 여러 개를 주지 않냐고. C++ 같은 경우는 while의 조건문 안에 cin 구문을 넣어주면 됩니다. cin 구문 자체적으로 입력을 받았을 때 true를 반환하기 때문입니다.
저 부분때문에 정답율이 엄청 낮은 것 같고, 알고리즘 자체는 복잡하지 않습니다. 오히려 너무 쉬워서 이게 골드 4라고? 라는 생각이 들 정도죠. 레고 조각의 차이의 절댓값이 가장 큰 것을 출력하라고 했으므로, 크기 순대로 나열하여 작은 것과 큰 것을 짝 맞춰주면 됩니다. 한 조각 씩 기준으로 정해서 이분 탐색을 하며 맞는 다른 조각을 찾는 방법도 있던데, 제가 둘 다 해봤을 땐 이 방법이 더 빠르더라구요.
- 나노미터 기준으로 비교하기 위하여 구멍의 크기에 10,000,000를 곱한다. 큰 수처럼 보이지만 전체적으로 int의 범위는 벗어나지 않으므로 long long형으로 선언하지 않아도 된다.
- 레고 조각을 크기 순으로 정렬한다. (algorithm 헤더의 sort() 함수
- left = 가장 작은 조각의 인덱스 = 0, right = 가장 큰 조각의 인덱스 = N - 1로 시작한다.
- left와 right를 더했을 때, 구멍의 크기보다 작으면 left를 1 늘려주고 (다음으로 큰 레고 조각), 구멍의 크기보다 크면 right를 1 감소시킨다. (다음으로 작은 레고 조각)
- 두 조각을 더했을 때 구멍의 크기와 같으면 바로 'yes'와 레고 조각의 길이를 출력하고, left가 right보다 커지면 반복을 종료하고 'danger'를 출력한다.