코딩테스트 연습 - 달팽이는 올라가고 싶다

코팅테스트 > 기본수학1 > 달팽이는 올라가고 싶다 (백준 : 2869)
학습플랫폼 : 백준

문제설명

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, H가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ H ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

제한사항

시간 제한 0.15초, 메모리 128 MB

입출력 예시

해결방법

처음 해당 문제를 접했을 때는 while을 통하여 반복으로 풀면 될 것 같아 무한 루프를 돌려
문제를 해결하였다. 하지만 제한 사항인 실행시간 0.25초에 걸려 시간초과가 뜨게 되어 다른 방법을
찾아야했다. 고민을 한 결과 이것은 수학식을 만들어 풀어야한다는 결론이 들었고 규칙을 찾아
수학식을 만들었다.

달팽이가
1일차에 올라가는 길이는 A만큼 올라간다.
2일차에 올라가는 길이는 (A - B) + A
3일차에 올라가는 길이는 (A - B) + (A - B) + A
....

이렇게 규칙이 생기는 것을 보아 수학식으로 변경을 하면 (N - 1)(A - B) + A 로 변경이 가능하다.

이것을 간소화 하면 NA - NB - A + B + A = H로 되고 정리하면
=> NA - NB + B = H
=> N(A - B) + B = H
=> N = (H - B)/(A - B) 로 수학식이 만들어 졌다.

N이라는 것은 달팽이가 목표까지 도달하는데 걸리는 최소 일수를 의미한다.
예시 1번을 대입하면 (5 - 1)/(2 - 1) = 4 로 최소 4일이 걸린다.
이때 조심해야할 점은 (5 - 1)%(2 - 1) 를 수행하였을 때 나머지가 0이되야 다음날 달팽이가 더이상 오르지 않아도 되기 때문에 나머지 연산을 통해 남은 일 수 가 있는지 확인 하는 작업을 진행한다.
남은 날이 있으면 +1일을 추가적으로 연산하여 수행한다.

해결코드

import java.util.*;
import java.io.*;

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());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
       
        System.out.println(((h-a)%(a-b)==0)?(h-b)/(a-b):(h-b)/(a-b)+1);
        
    }
}