Close
Close full mode
logo만렙 개발자 키우기

징검다리 건너기

Git RepositoryEdit on Github
Last update: a year ago by nowwaterReading time: 2 min

문제

코드

코드 보기
import java.util.Scanner;
public class intern20195 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt(), stones[] = new int[10];
for (int i = 0; i < 10; i++) {
stones[i] = sc.nextInt();
}
Solution sol = new Solution();
System.out.println(sol.solution(stones, k));
}
}
class Solution {
static int[] stones;
static int k;
public int solution(int[] mstones, int mk) {
stones = mstones; k = mk;
int left = 1, right = 200000000;
while(left < right){
int mid = (left + right) / 2;
if(checkCondition(mid)) right = mid;
else left = mid + 1;
}
return left;
}
private boolean checkCondition(int m) {
for (int i = 0; i < stones.length; i++) {
if(stones[i] - m <= 0){
if(i + k - 1 >= stones.length) break;
boolean flag = true;
for (int j = i + 1; j < i + k; j++) {
if(stones[j] - m > 0) {
flag = false;
i = j;
break;
}
}
if(flag) return true;
}
}
return false;
}
}

⭐️느낀점⭐️

카카오 기출 문제와 백준 기출 문제는 느낌이 다르다는 것을 알았다.

다양한 알고리즘 유형이 나오지만 또 풀이방법이 어려운 건 아닌 깔끔하고 진짜 다양한 문제의 요구 사항을 맞추는 문제인 듯 하다.

풀이 📣


1️⃣ 최대한으로 징검다리를 건널 수 있는 인원을 구하기 위해 이분탐색을 실시한다.

- 각 돌다리의 수명이 2억 이하인 자연수이므로, 최대로 건너갈 수 있는 인원 m 도 2억명이다.

2️⃣ 현재 최대 인원이 돌다리를 지날 수 있는지 확인한다.

- 연속으로 k 개의 돌다리가 수명을 다했다면 다음 차례의 사람은 건너갈 수 없다.
- 한 명이 지나갈 때 마다 각 돌다리의 수명이 1씩 깎이므로, 연속된 k 개의 돌다리가 (수명 - m) <= 0 이라면 m 명보다 더 건널 수 없다.

3️⃣ 현재 인원mid보다 더 클 수 없다면 최대치 rightmid 값으로 변경해주고, mid 보다 많은 인원이 가능하다면 최소 인원leftmid + 1 로 변경해준다.

4️⃣ 최종적으로 구한 최대 가능 인원을 출력한다.


실수 😅

  • 돌다리의 수명이 2억이하이므로 모든 칸을 탐색하면서 1씩 줄이는 것은 불가능할 것이라 생각했다.

  • 나름대로 연산을 줄여보려고 우선순위 큐를 만들어서 한 번에 같은 수명을 가진 돌다리를 모두 지우고 사용 불가능함을 boolean 타입으로 표시해서 풀려고했다.

  • 그리고 연속되는 K 개의 돌다리가 수명을 다했는지 확인하는 식으로 했었다.

  • 하지만 이 방법은 인원수를 m이라고 하고 돌다리의 개수를 n 이라고 하였을 때 m*n^2*logn 이라는 어마어마한 시간이 걸린다

  • 따라서 다른 방법을 찾아보고 이분 탐색을 통해 nlogm 시간에 동작하는 풀이를 찾을 수 있었다.

👩‍💻 Problem Solving — Previous
호텔 방 배정
Next — 👩‍💻 Problem Solving
K 20203