문제

https://www.acmicpc.net/problem/2869

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class 달팽이는_올라가고_싶다 {
    public static void main(String[] args) throws IOException {
        String[] input = getInputData(System.in).split(" ");
        int[] abv = convertStringArrayToIntegerArray(input);

        System.out.println(solution(abv));
    }

    public static String getInputData(InputStream in) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(in))) {

            return br.readLine();
        }
    }

    private static int[] convertStringArrayToIntegerArray(String[] args) {
        int[] array = new int[args.length];
        int i = 0;

        for (String str : args) {
            array[i++] = Integer.parseInt(str);
        }

        return array;
    }

    public static int solution(int[] abv) {
        return (abv[2] - abv[1] - 1) / (abv[0] - abv[1]) + 1;
    }
}

흐름

  1. 달팽이는 하루에 A 만큼 올라가는데 자면서 B만큼 미끄러지므로 하루에 (A - B) 만큼 씩 올라가서 V미터 만큼 올라가면 된다.
  2. 하지만 꼭대기에 도달하면 미끄러지지 않는다고 하였으므로, 꼭대기(V) 에서 미끄러지는 만큼(B) 을 뺀 거리만큼만 올라가면 된다. (V - B)
  3. 그럼 수식은 (V - B) / (A / B)가 되고 int형은 소수점을 없애므로 나누어떨어지지 않으면 + 1을 하는데
  4. (V - B)에서 - 1을 먼저하고 무조건 1을 더한다.

(V - B - 1) / (A - B) + 1

  • V-B를 X, A-B를 y로 가정
  1. x/y가 나누어 떨어지는 경우
    1. x / y = d 일 때 (x-1)/y 는 반드시 d보다 작다.
    2. int형은 소수점 아래를 없애므로 x-1 /y = d - 1이 되고,
    3. +1을 하면 d가 된다.
  2. x/y가 나누어 떨어지지 않는 경우
    1. x / y = d + f 일 때 y를 양변에 곱하면
    2. x = y(d + f) 여기서 양변에 1을 빼면,
    3. x - 1 = y(d + f) - 1 여기서 y를 양변에 나누면
    4. (x - 1) / y = (d + f) -1 / y 이 된다.
    5. 이 때 1 / y 는 y >= 2 이고 int형은 소수점 아래를 없애버리므로 1 / y 는 없어진다.
      1. y >= 2 인 이유는 현재 x / y가 나누어 떨어지지 않는 경우임을 상정하고 있으므로 y가 1이면 나누어 떨어지기 때문에 y는 2보다 크게 된다.
    6. 그럼 (x - 1) / y = d + f 이 되고 +1을 하면,
    7. (x - 1) / y + 1 = d + f + 1 된다.

결과

결과

테스트 케이스

1
2
3
4
5
6
7
assertEquals(4, test.solution(new int[] {2,1,5}));
assertEquals(2, test.solution(new int[] {5,1,6}));
assertEquals(999999901, test.solution(new int[] {100,99,1000000000}));
assertEquals(1, test.solution(new int[] {5,0,5}));
assertEquals(4, test.solution(new int[] {3,2,6}));
assertEquals(2, test.solution(new int[] {100,1,101}));
assertEquals(3, test.solution(new int[] {3,1,6}));

참고 사이트