[C] 1654 - 랜선 자르기

김태희·2025년 5월 6일

C / 자료구조 / 알고리즘

목록 보기

34/39

[C] 1654 - 랜선 자르기

대학에 복학해 자료구조 수업을 들으며 기본기를 다지고 시험 공부에 열중하면서도 남는 시간에는 백준 문제를 풀고 있다.

학점 4.5를 받고 남는시간에 짬짬이 코딩테스트를 풀면서 백준 골드까지 가는것이 이번 학기 목표이다. (현재 실버 2)

그래서 좀 코딩테스트나 대학 수업에서 배운 내용들중 오래 기억하고싶은 내용들은 벨로그에 기록해가면서 공부하려고한다.

시간초과 이슈

#include <stdio.h>

int main(void){
  int arr[10000];
  int index[10000];
  int n, k, max=0, sum=0;

  scanf("%d %d", &k, &n);
  for(int i=0; i<k; i++){
    scanf("%d", &arr[i]);
    if(max<arr[i]) max = arr[i];
  }
  max /= 2;
  while(max){
    sum = 0;
    for(int i=0; i<k; i++){
      sum += arr[i] / max;
    }
    if(sum>=n) break;
    max--;
  }
  printf("%d", max);
}

이 문제에는 두가지 신경써야할 부분이 있다.

시간초과 문제 -> 이진 탐색(Binary Search)으로 해결
자료형의 범위초과 -> long long 자료형을 사용하여 해결

처음엔 위와 같은 방법으로 단순히 가장 긴 줄의 절반(k<=n 이므로 절반부터 탐색한다.)으로 각 줄의 길이를 나누어서 n보다 큰값을 가질때까지 max--;를 실행하는 알고리즘을 구현했다.

하지만 결과는 시간 초과였고 다른 방법을 찾아보니 이진 탐색을 사용하면 시간 복잡도가 O(log n)으로 줄어들어 탐색 시간을 줄일 수 있다는 내용을 알게 되었다.

최종 코드

#include <stdio.h>

int main(void) {
  long long arr[10000];
  int n, k;
  long long left, mid, right, sum, max_len=0, max = 0;

  scanf("%d %d", &k, &n);
  for (int i = 0; i < k; i++) {
    scanf("%lld", &arr[i]);
    if (max < arr[i])
      max = arr[i];
  }

  left = 1;
  right = max;
  while (left<=right){
    mid = (left+right)/2;
    sum = 0;
    for (int i = 0; i < k; i++) {
      sum += arr[i] / mid;
    }
    if(sum>=n && max_len<mid)
      max_len = mid;
    if(sum<n)    
      right = mid-1;
    else  
      left = mid+1;
  }
  printf("%lld", max_len);
}