https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.
www.acmicpc.net
요즘 프로젝트로 biginteger를 다루는 자료형을 만들었었는데
이것의 부작용인지..... 문제를 처음 봤을때 조건들의 숫자가 그렇게 크지 않다고 생각하고 아무렇게나 접근했었는데
위와 같이 큰 수부터 1씩 감소 시켜주면서 잘라서 개수를 비교하여 처음 N 과 같아질때의 수를 출력하는 식으로 했더니?
채점중 2퍼인가 에서 시간초과...5퍼인가?.....
꽤 채점이 되다가 시간초과가 떳으면 이 코드에서 시간을 줄여보고자 생각을 했을 수도 있겠지만
터무늬 없어서 방법을 바꿔야 한다는 것을 깨닫고 문제 조건을 다시 파악했다....
무엇이 좋을까 하다가 떠오른건 "이분탐색"
코드의 디테일 까지는 잘 생각이 안나서 짜면서 신경 써야되는 부분이 있지만
역시 개념자체는 배워놓으면 잘 까먹지 않고 생각 나는 것 같아서 혼자 뿌듯....
이분 탐색으로 짠 코드는 다음과 같다.
간단해서 따로 설명할 것은 없어보이고
길이는 1이상 이기때문에 처음 bottom값을 0으로 설정하면 채점중 런타임 에러가 나타난다. <주의>
'학부생 공부 > 연습문제(백준)' 카테고리의 다른 글
| 백준 10995 (0) | 2019.12.30 |
|---|---|
| 백준 15947 (0) | 2019.12.30 |
| 백준 10818 (0) | 2019.12.25 |
| 백준 10757 큰 수 A+B (0) | 2019.11.24 |
| 백준 10989 수정렬하기3 (0) | 2019.11.16 |