[8주차_화요일] 흙길 보수하기

[baexxbin]

• 사이트 : 백준(BOJ)
• 문제: 흙길 보수하기
• 번호: 1911

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 10,000 → 10^4라서 O(N^2)까지 가능
• 시간 제한이 2초이므로 딱히 신경쓰지 않음

💡 풀이 아이디어

• 판자를 놓은 마지막 좌표를 기억하여 추가로 몇 개를 사용해야 하는지 확인
• 현재 웅덩이가 이전에 덮은 판자로 덮혀있다면 스킵

  for (int i = 0; i < n; i++) {
  // 이미 덮혀있다면 스킵
  if (arr[i][1] < prev)
      continue;
  // 시작 좌표가 덮혀있는지 확인하여 최댓값으로 시작 좌표 계산
  prev = Math.max(prev, arr[i][0]);
  double len = arr[i][1] - prev;      // 덮어야하는 웅덩이의 남은 길이
  int cnt = (int) Math.ceil(len / l); // 사용해야하는 판자의 수
  total += cnt;    // 사용한 판자 수
  prev += cnt * l; // 마지막 좌표 기억
  }

  문제에서는 위치라고 주어져서 양 끝 포함하는 줄 알았는데 시작값만 포함하는 좌표였네요..

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= 물웅덩이의 개수 <= 10,000
• 1 <= 물웅덩이로 덮을 수 있는 길이 <= 1,000,000
• 0 <= 각 위치 <= 1,000,000,000

반복문을 잘못 쓰면 시간 초과가 발생할 수 있음! 그리디적으로 풀이하여 물웅덩이의 개수 만큼만 시간을 사용할 수 있도록 함

💡 풀이 아이디어

• Node: 물웅덩이의 시작점과 끝점 저장
• 물웅덩이의 시작점 기준으로 정렬
• 물웅덩이가 시작하는 지점 기준으로 널빤지를 몇 개 깔아야 되는지 계산

• 널빤지가 끝점을 넘어가는 경우와 이 경우로 인해 다음 널빤지의 시작점을 넘는 경우 주의하기!

  Arrays.sort(nodes, (o1, o2) -> Integer.compare(o1.s, o2.s));
  
  int current = 0, cnt = 0;
  for(Node n: nodes) {
    if(current < n.s) {
        current = n.s;
    }
  
    while(current < n.e) {
        current += L;
        cnt++;
    }
  }

[baexxbin]

🤔 시간복잡도 고려사항

• N(1 ≤ N ≤ 10,000)
• L(1 ≤ L ≤ 1,000,000)
• 완전탐색 가능

💡 풀이 아이디어

• 널판지 길이가 정해져있기에 순서대로 널판지 놓아가기
• 웅덩이 좌표 정렬
• start: 놓아야할 널판지 시작점
  • 이미 덮어진 웅덩이면 패쓰 : if (start >= p.e)
  • 놓여진 널판지, 현재 웅덩이 시작 중 큰 값을 기준으로 다음 널판지 놓기 : int curStart = Math.max(start, p.s)
• 널판지 개수는 (끝-시작)/L + (나머지 여부)
• start는 curStart + need * L로 업데이트

[yeongleej]

🤔 시간복잡도 고려사항

• 물웅덩이 개수 : N ≤ 10,000
• 널판지 길이 : L ≤ 1,000,000

O(N)으로 완전탐색 가능

💡 풀이 아이디어

• 물웅덩이 정렬 : 시작점 순으로 정렬
• 이분탐색 이용
  • 구해야 하는 것: 최소 널판지 개수
  • e : 최대 널판지 수(L이 1일 때, 가장 마지막 물웅덩이까지 덮을 경우)
  • 결정 문제 : mid개의 널판지로 모든 물웅덩이를 덮을 수 있는가
  • 정렬된 널판지를 차례대로 탐색하면서 필요한 널판지 개수 구함

N이 작으니깐 완전탐색이나 그리디로 풀면되네요!

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 그리디
• 시간복잡도: 웅덩이 갯수 N(1 ≤ N ≤ 10,000)
• 웅덩이의 갯수만큼 반복 O(N)

💡 풀이 아이디어

1. TreeMap 을 통해 시작점을 기준으로 오름차순 정렬하며, 시작점이 겹칠 경우 마지막 지점이 더 큰 값을 value 로 지정
2. 웅덩이의 시작, 끝 위치가 겹치는 부분이 생겼을 때 널판지가 중복해서 계산되는 경우를 제외하고 생각해야함 2-1. 마지막 지점에 이미 널판지를 설치했을 경우 2-1. 처음 지점에 널판지가 겹쳐지게 될 경우

3. 여분 널판지가 더 필요할 경우 보충한 만큼 길이 추가

   result += (end- length)/L;  //필수 널판지길이
   int reminder = (end- length)%L; //여분 널판지 길이
   length = end;
   
   if(reminder != 0){
       result++;
       length += L - reminder; //여분 널판지를 보충한 만큼 길이 추가
   }

[icegosimperson]

🤔 시간복잡도 고려사항

N<=10,000, L<=1,000,000 -> O(N) 이하 가능

💡 풀이 아이디어

• 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력
• 시작 위치로부터 순서대로(->정렬) 물웅덩이를 덮어 나가기 -> 그리디
• 람다식을 사용해서 오름차순 정렬
  • 시작 위치부터 순서대로 덮기 위함
  • Arrays.sort(puddles, (a, b) -> Integer.compare(a[0], b[0]));
• 반복문을 사용해서 물 웅덩이 덮기 시작
  • 현재 위치를 널빤지가 이미 덮었다면(current >=e) 널빤지 필요X -> 지나감(continue)
  • 아닌 경우(current < s) -> 물웅덩이 시작 위치부터 덮기
• result : 필요한 널빤지 계산
• 덮은 위치 갱신 후 최소 널빤지 개수 출력