[백준] 장난감 경주 19592번

문제 링크 : https://www.acmicpc.net/problem/19592

 

이진 탐색으로 얼만큼의 최대 부스터를 사용할지 정하는 문제이다.

부스터의 길이를 이진 탐색 대상으로 놓고 코드를 작성해보았다.

package baekjoon;

import java.util.Scanner;

public class ToyCompetition_19592 {

    private static int solved(int N, int X, int Y, int v[]) {

        double arr[] = new double[v.length];
        double min = X;

        //나머지 배열 중 가장 적은 값 찾아내기 (소수점 자리 안버리고)
        for(int i=0; i<v.length; i++) {
            arr[i] = X/v[i];
            if(min>arr[i]) {
                min = arr[i];
            }
        }

        if(min==arr[v.length-1]){
            return 0;
        }

        //이진탐색으로 찾아내기
        int start = 1;
        int end = Y;
        int mid;
        //몇 초 걸리는지
        double tmp;

        while(start<=end) {
            // mid : 부스터 속력
            mid = (start+end)/2;
            // tmp : 부스터를 사용하였을 때에 걸리는 시간.
            tmp = (12-mid)/v[v.length-1];

            if(min < tmp) {
            // 반으로 나눴을 때, 오른쪽에 있는 경우 (부스터를 썼음에도 여전히 1등 못한 경우)
                start = mid + 1;
           //     System.out.println(start+" "+end);
            } else if(min > tmp) {
            // 부스터를 썼을 때 1등한 경우 (그럼에도 최소 수치를 찾아야 함.)
                end = mid;
           //     System.out.println(start+", "+end);
            } else {
                return mid + 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);

        int n = 3;
        int x = 12;
        int y = 11;
        int vec[] = {3,2,1};

        int ans = solved(n,x,y,vec);
        System.out.println(ans);

        //scanner
//        int T = sc.nextInt();
//        int vec[] = new int[3];
//        for(int i=0; i<T;i++) {
//            int N = sc.nextInt();
//            int X = sc.nextInt();
//            int Y = sc.nextInt();
//
//            for(int j=0; j<3; j++) {
//                vec[j] = sc.nextInt();
//            }
//        }

//        sc.close();
    }
}

일단 처음 작성했을 때의 문제는

1. 정답이 출력되지 않은 것 (사실 틀렸다고 보면 됨.)

2. 나누기로 계산을 하기 때문에 소수점으로 딱 떨어지지 않는 경우 마지막 else 구문에서 애매해질 수 있다는 점이다.

3. 공동 우승일 때의 경우 고려

 

고민을 해보고 다시 이진 탐색을 손코딩 했을 때, 문제를 읽는 과정에서 잘못 파악한 것을 확인했다.

Y m/s 만큼 1초간 이동한 것이기 때문에 tmp 변수에 값을 넣어줄 때 +1을 해줘야 했다! (1번 해결)

---

3번의 경우도 더불어서 다시 생각해봤다.

if(min < tmp) {
// 반으로 나눴을 때, 오른쪽에 있는 경우 (부스터를 썼음에도 여전히 1등 못한 경우)
    start = mid + 1;
} else if(min > tmp) {
// 부스터를 썼을 때 1등한 경우 (그럼에도 최소 수치를 찾아야 함.)
    end = mid;
} else {
    return mid + 1;
}

else 조건은 v[i]를 제외한 나머지 장난감 중에서 가장 적게 걸리는 시간을 min 변수에 넣은건데 

min과 tmp가 같다는 것은 공동우승한다는 것이다. (공동 우승의 경우를 생각 안함.)

mid+1을 리턴하는게 답이 될 수 있을까? 

 

else 조건(min==temp)에서 다시 if 문을 추가해보았다. 

else {
    if(mid==Y)
        break;
    else
        return mid+1;
}

최대로 쓸 수 있는 부스터 속력은 Y로 만약 찾고자하는 mid가 Y랑 같다는 조건을 추가하였다.

이렇게 추가하면 break로 while문에서 빠져나와 -1을 리턴한다.

 

---

2번의 경우가 조금 복잡했다.

처음에는 if와 else if로 넘어가는 순간의 값을 찾아야 한다고 생각했다.

 

조금 더 고민하다가 수정해서 올리겠다.