[Dev-Ping9] 백준 2869번 - 달팽이는 올라가고 싶다 (Java)

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

---

# 문제 설명

• 달팽이가 귀엽다... 미끄러진다니... 
• 시간제한 0.15 초 이므로 Brute-Force로는 못품 (for문을 돌리는 순간 통과 안될 것)
• 규칙을 찾자! 이왕이면 식으로 바로 구할 수 있어야 0.15초를 뚫을 것이다.

 

# 규칙 (식)

• 하루동안 달팽이가 올라가고 미끄러진 높이는 A-B (달팽이의 속력)
• 정상에 올라서면 -B 가 발생하지 않음 (딱 한번만 B가 제외된다는 뜻)
• 그럼 올라갈 나무 높이에서 미리 -B를 해주면 됨 (미끄러졌다는 건 올라갈 나무높이가 더 길어졌다는 건데, 더 짧게 만들어주는 것)
• day = (tree-B) / (A-B) 가 성립 (올림 처리를 해줘야 한다. 9미터를 4의 속도로 올라가면 3일이 걸리기 때문)
• 아래의 식으로도 유도 할 수 있다. 
  // up = A-B(day)+B
  // day= (up-B) / (A-B)
  // up = A*day - B*(day-1);  달팽이가 N일 동안 올라가는 높이

 

---

# 구현코드 (Java)

import java.io.BufferedReader;
import java.io.IOError;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer( br.readLine()," ");
        long A = Integer.parseInt(st.nextToken());
        long B = Integer.parseInt(st.nextToken());
        long tree = Integer.parseInt(st.nextToken());
        // 1<= B < A <= tree <= 1_000_000_000 //10억 100m = 1b
        
        //Time limit 0.15sec; for java        
        long day;        
        day = (long)Math.ceil((double)(tree-B) / (A-B)); 
        System.out.println(day);
        
        //Brute-Force
        // int up=0;
        // for(day=1;; day++){
        //     up += A;
        //     if(up>=tree) break;
        //     up -= B;
        // }
    }
}