2869_달팽이는 올라가고 싶다 (JAVA)

2869번: 달팽이는 올라가고 싶다

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int day = sc.nextInt();
		int night = sc.nextInt();
		int h = sc.nextInt();

		//무엇을 찾을 것인가? 며칠 걸리는지(걸리는 일수)
		int left = 0; //최소 범위? 1일
		int right = h; //최대 범위? h+1일
		int mid = 0;
		int ans = 0;
        
		while(left<=right){
			mid = (left+right)/2;

			//1일차 낮에 h에 도달하는 경우부터 시작해서 mid값 예측
			if((mid-1)*(day-night)+day < h){
				left = mid+1;
			}		
			else {
                right = mid-1;
                
                //(mid-1)*(day-night)+day == h 인 경우가 없을 때를 대비해서 mid값 저장
                ans = mid; 
            }
		}
		System.out.println(ans);
	}
}

 

이분탐색으로 생각하는거 어렵다ㅠㅠ  알듯 모를듯 하다가 모르겠다ㅠㅠ 

 

 

[문제 풀이 생각 과정]

 

아주 단순하게 while문 안에 if문으로 풀었더니 - 시간초과가 났다. '이분탐색으로 꼭 풀어봐야하는 문제'라길래 냉큼 풀어보기!

 

1. 무엇을 찾을 것인가? '며칠' 걸리는 지

     찾을 값 = mid 로 놓고 이분탐색으로 풀기! ( 예: mid<h이면 left=mid+1; 방식으로 mid값을 에측하면서 이분탐색 하기 )

 

2. '며칠'의 범위?

     (mid - 1) * ( day - night ) + day 값을 기준으로 판단한다.

     최소 = left = 0 : 1일차에 낮에 h에 도달한 경우로, mid=1일때가 최소 (1일 걸릴때)

     최대 = right = h : 문제의 조건에서 B<A 이므로 하루에 최소 1씩 올라간다

                                      - 그렇기 때문에 하루씩 h일 걸릴때, h+1일차에 낮에 h에 도달한 경우가 최대 걸리는 일수 

 

3. (mid - 1) * ( day - night ) + day == h 인 경우가 없을 수 있다.

      이때를 대비해서 mid값을 저장한 상태로 반복문 돌리기!