📜문제 설명
집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.
이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
📍입력
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.
4 11
802
743
457
539📍출력
첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.
200📄문제 해결
📝내가 푼 코드
1차 시도
k, n = map(int, input().split(' '))
lengths = [int(input()) for _ in range(k)]
a = sum(lengths)//n # 초기 길이
while True :
cnt = 0
for length in lengths:
cnt += length//a
if cnt >= n: break
else: a -= 1
print(a)문제는 조건에 맞는 최대 길이를 구하는 것이므로, 최대한 답에 근접할 초기 길이를 구하고, 반복문을 통해 답을 탐색하도록 하였다. 정답은 잘 구해졌지만 제출한 뒤 시간 초과라는 문제에 부딪혔다. 곰곰히 생각하다가 도무지 시간복잡도를 절약할 방법이 생각나지 않았기에 chatGPT에게 도움을 받았다. 😂
2차 시도 -> 성공
k, n = map(int, input().split(' '))
k, n = map(int, input().split(' '))
lengths = [int(input()) for _ in range(k)]
low, high = 1, max(lengths)
result = 0
while low <= high:
mid = (low + high) // 2
cnt = sum(length // mid for length in lengths)
if cnt >= n:
result = mid # 조건을 만족하므로 결과값 업데이트
low = mid + 1 # 더 큰 길이를 탐색
else:
high = mid - 1 # 더 작은 길이를 탐색
print(result)chatGPT는 나의 코드를 이진 탐색으로 최적화할 수 있다고 알려주었다. 이때, 나는 문제가 의도한 바를 정확히 파악하지 못했다는 것을 깨달았다.
문제에서는 정답에 대해 주어진 범위(1 ~ k개 랜선 중 최대 길이)가 존재하고, 그 길이로 랜선을 잘랐을 때 랜선의 개수가 n개 이상이 되어야 한다는 조건을 제시한다. 이것은 곧, 우리가 1부터 100까지의 정수 중에서 특정 정수를 탐색한다고 할 때 필요한 조건과 같다. 1부터 100이 주어진 범위이며, 선형 탐색을 한다고 하면 비교할 숫자와 우리가 찾는 숫자가 같아야한다는 것이 조건이다.
따라서, chatGPT가 선형 탐색으로 작성한 나의 이전 코드를 바탕으로 이진 탐색을 적용하여 최적화하는 방법을 제시해준 것이라고 생각해볼 수 있다.
🤔느낀점
오늘 문제를 풀고, chatGPT를 활용해 최적화된 코드를 이해하면서 스스로가 코딩테스트를 연습할 때 문제에서 원하는 바를 제대로 생각하지 않고, 문제에서 제시하는 로직을 구현하기 위한 과정만 중점적으로 생각하고 있었다는 것을 깨달았다.
최적화 과정에서 스스로가 간과했던 것도 내가 짠 코드가 어떤 알고리즘을 적용한 것인지 정확히 인지하지 못했다는 점이었다. 내가 이전에 짰던 코드는 탐색 중에서도 선형 탐색 이라고 말할 수 있는데, 나는 그저 이렇게 하면 되지 않을까? 라고 생각하고 코드를 짰기 때문에 명확히 이 문제에서 말하고자 하는 의도가 탐색임을 인지하지 못했다. 따라서, 이전에 짠 코드가 선형 탐색이라는 것도 제대로 인지하지 못했기에 이진 탐색이라는 알고리즘을 적용해 시간복잡도를 최적화할 수 있다는 생각까지 이어지지 못했던 것이다.
만약 탐색에 대한 문제였다는 것을 인지했다면 자연스럽게 이진 탐색으로 최적화가 가능할 것이라는 생각으로 이어지지 않았을까 하는 아쉬움도 든다. 비록 chatGPT의 도움을 받았지만 오늘의 깨달은 것이 다음에 코딩테스트 문제를 풀 때 더욱 좋은 방향으로 공부할 수 있게 이끌어줄 것이라 믿는다! 인생은 방향이니까 말이다.
