[백준 - 2869] 달팽이는 올라가고 싶다 - Java

문제 설명

 

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

 

접근 방법

수학적으로 공식을 세워 푼 문제로 다소 직관적이진 않지만 한번의 연산으로 아주 빠른 시간 내 정답을 도출할 수 있는 방식을 도출했습니다. (많은 문제들을 이런 식으로 공식을 세워 풀고 싶지만 이런 공식은 바로바로 세워지지 않네요.. 😅)

 

우선 공식을 세우기 위한 규칙성을 찾기 위해 A와 B 값은 그대로 두고 V값을 1씩 증가시켜보았습니다.

 

A = 5, B = 1, V = 5인 경우입니다.

A	B	V	Day
5	1	5	1
5	1	6	2
5	1	7	2
5	1	8	2
5	1	9	2
5	1	10	3

 

위 표를 보면 A와 V가 같을 때는 Day가 1임을 알 수 있는데, 달팽이가 정상에 도달한 후에는 미끄러지지 않으므로 첫 날에 정상에 도달한 것으로 볼 수 있습니다. 이후에는 묘한 규칙성이 느껴지는데, Day가 2로 4번 반복됩니다. 여기서는 표가 길어져 생략했지만 그 이후에도 Day는 3으로 4번 반복됩니다.

 

여기서 반복되는 숫자 4는 A - B의 값으로 추정해볼 수 있었습니다. 왜냐하면 목표값 V가 A와 동일할 때는 Day 1에 종료되지만 목표값 V가 A보다 1만 더 커져도 2일이 걸리는데, Day 1 이후 달팽이의 위치가 4였으므로(밤에 1만큼 후퇴했으닌까) 목표값이 적어도 9(A-B+A)까지는 어찌됐든 2일이 걸리게 됩니다. 즉, 첫 날을 제외하고 나머지 일수에는 4(=A-B)만큼은 2일이 걸리는 것입니다.

 

이처럼 Day가 반복적으로 나오는 일종의 힌트를 발견할 수 있었고, 다음은 Day에 대한 공식을 세울만한 결정적인 단서를 찾아야 했습니다. Day가 2일 때 V-B는 5, 6, 7, 8로 1씩 증가하는 것을 알 수 있는데(당연히 V가 1씩 증가하고 있으닌까) 아까 발견했던 힌트에서 A-B(=4)로 각각 나누면 1.xx 로 몫이 일정하다는 것을 알 수 있습니다. 몫은 일정하닌까 나머지만 올림 처리함으로써 Day에 대한 공식을 Math.ceil((V-B)/(A-B))로서 도출할 수 있었습니다.

 

A = 5, B = 2, V = 5인 경우에도 동일한 규칙성이 나타남을 알 수 있습니다.

A	B	B	Day
5	2	5	1
5	2	6	2
5	2	7	2
5	2	8	2
5	2	9	3
5	2	10	3
5	2	11	3
5	2	12	4

 

전체 소스 코드

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

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()), b = Integer.parseInt(st.nextToken()), v = Integer.parseInt(st.nextToken());

        System.out.println((int) Math.ceil( (double) (v - b) / (a - b)));
    }
}

 

참고자료

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