[4주차_수요일] 1477_휴게소 세우기

[yeahdy]

• 사이트 : 백준(BOJ)
• 문제: 휴게소 세우기
• 번호: 1477

[Jewan1120]

🤔 시간복잡도 고려사항

• 제한이 널널해서 따로 신경쓰지 않았음!

💡 풀이 아이디어

• 매개 변수 탐색 → 특정 조건을 만족하는 최대 or 최솟값을 찾는 이분 탐색
• 현재 문제는 최댓값들 중 최소이므로 조건을 만족하는 값들의 Lower Bound를 찾으면 됨
• 매개 변수는 휴게소가 없는 구간이므로 해당 값을 기준으로 이분 탐색 진행
• 타겟이 되는 값으로 각 구간마다 휴게소가 몇 개 세워지는 지에 따라 경계 설정
  • 검사 조건에 true를 반환한다면 오른쪽 경계를 변경
• 마지막 true를 반환하는 시점에서의 왼쪽 경계를 출력

비교적 최근에 한번 풀어봤던 문제라 빨리 접근할 수 있었습니다🐹

[baexxbin]

🤔 시간복잡도 고려사항

• 0 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• 100 ≤ L ≤ 1,000
• 이분탐색으로 풀기에 제한 조건 충분

💡 풀이 아이디어

스터디하면서 연습했던 이분탐색 문제 유형!

• 이분탐색 내용: 휴게소 간 거리 (distance)
• 이분탐색 조건: 거리 (distance)로 휴게소를 지었을때 갯수가 맞는지 >> canBuild()
  • canBuild() : 휴게소간 거리를 배열을 돌며, 해당 거리에 휴게소가 몇개 들어갈 수 있을지 세기
    • 이때 휴게소 간 거리%distance==0이면, 기존 휴게소랑 겹치기에 -1해주기
  • canBuild()로 M개 보다 많이 휴게소를 지을 수 있다면, 거리 늘리기 left = distance-1

canBuild()함수에서 return cnt>M; 조건에 =여부 때문에 시간이 시간이 오래걸렸다..! 이분탐색에서 조건 확인 잘하기!! 그리고 계산의 문제인지, 그냥 ans값을 반환하면 값이 -1 적게 나와서 ans+1값으로 반환해주었습니다..!

[KodaHye]

🤔 시간복잡도 고려사항

• 현재 휴게소의 개수: 0 <= N <= 50
• 추가로 지을 휴게소의 개수: 1 <= M <= 100
• 고속도로의 길이: 100 <= L <= 1000
• 휴게소의 위치: 1 <= 휴게소의 위치 <= L - 1

완전 탐색으로 문제 풀이를 한다면 1000C100의 경우가 발생할 수 있음. 완전 탐색이 아닌 다른 방법으로 문제풀이해야 함 이진 탐색으로 풀이한다면 O(log1000)로 풀이 가능

💡 풀이 아이디어

• 총 설치할 수 있는 휴게소의 개수를 구하면서 휴게소 사이 최대 간격을 조절하기
• 최대 간격을 중 최솟값을 구해야 되므로 lowerIdx를 구해야 함
• int getRestCnt(int dis)
  • dis 간격일 때, 설치할 수 있는 휴게소의 개수를 구하는 함수
  • (현재 위치 - 이전 위치 - 1) / dis
  • 현재 위치와 이전 위치에 휴게소를 세울 수 없으므로 -1을 해줌

문제에서 요구하는 사항에 따라 upperIdx를 구해야되는지, lowerIdx를 구해야되는지 적절하게 따지고 구하기!

[yeongleej]

🤔 시간복잡도 고려사항

• N ≤ 50
• M ≤ 100
• L ≤ 1,000 : 시간은 넉넉하지만 완전탐색은 X

💡 풀이 아이디어

• 구해야 하는 것: 휴게소의 간격의 최솟값 == mid
  • 이분탐색으로 세울 수 있는 휴게소를 탐색해 간격의 최솟값 찾음
• 휴게소 정렬하기
• 세울 수 있는 휴게소 구하기
  • arr[i-1]번째 휴게소와 arr[i]번째 휴게소 사이에 mid의 간격으로 세울 수 있는 개수 카운트
  • 총 개수가 M보다 작거나 같으면 기록 후, 간격 늘림
  • 크다면, 개수가 초과된다는 것이므로 간격을 줄임

처음에는 단순하게 우선순위 큐를 사용해서 간격의 1/2 지점에 설치할려고 했지만, 휴게소는 여러개 설치될 수 있기 때문에 이는 잘못된 문제 이해였습니다,,,, 문제를 좀 더 꼼꼼히 읽고, 이분탐색 제어 함수와 lower bound, upper bound 찾는 방법을 더 공부해야 할 것 같습니다.... ㅎㅎㅎ

[icegosimperson]

🤔 시간복잡도 고려사항 완전 탐색 시 시간 복잡도 : 950C2 (현재 휴개소가 있는 위치 제외) -> 너무 큼 이분 탐색으로 시간 복잡도를 줄여줘야함 -> O(log N)

💡 풀이 아이디어 휴게소가 없는 구간의 최댓값의 최솟값을 출력하는 문제 최댓값의 최솟값을 갱신하며 적절한 휴게소의 위치를 찾아야함 -> 이분 탐색

1. 고속도로의 시작점(left) = 0 ~ 고속도로 끝점(right) L 탐색
2. mid 값 기준으로 각 구간을 나누고, mid 값 이하로 만들기 위해 cnt(필요한 휴게소 개수)를 계산.
3. cnt > M일 때, left = mid + 1로 범위를 좁혀 더 큰 구간을 탐색. cnt <= M일 때, right = mid - 1로 범위를 좁혀 더 작은 구간을 탐색.
4. 탐색 종료 후 최종 값 left 반환

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 이분탐색
• 시간복잡도:
  • 제한시간: 2초
  • 0 ≤ N ≤ 50 O(NlogN) 정렬
  • 100 ≤ L ≤ 1,000 으로 O(logL) 이분탐색하기 충분한 시간

💡 풀이 아이디어

• 휴게소가 없는 최대 길이 구간에서 설치 가능한 최소 구간의 값
• 구간 탐색 범위: 1 ≤ 휴게소의 위치 ≤ L-1
• 중간 값: 휴게소의 처음 구간 + 휴게소의 마지막 구간 / 2
• buildCount > M 휴게소를 기준 값보다 많이 설치한다면, 최대값에서 최소값을 찾기 때문에 설치 갯수를 줄어야 한다.
• buildCount <= M 휴게소를 기준 값보다 적게 또는 동일하게 설치한다면, 최대 구간을 찾기 위해 설치 갯수를 늘려야 한다.

[KodaHye]

매개변수, 이분탐색 공부해보고 얘기해보기

이제까지 문제 푼 것들 범위설정 어떻게 했는지 생각해보고, 얘기하는 시간 갖기