https://www.acmicpc.net/problem/2869
문제
> 땅 위에 달팽이가 있다.
> 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.
> 달팽이는 낮에 A미터 올라갈 수 있다.
> 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다.
> 또, 정상에 올라간 후에는 미끄러지지 않는다.
> 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.접근
달팽이가 정상에 도달하면 더 이상 미끄러지지 않는다. 이말은 즉, 오를 수 있는 경우인 낮에 정상에 오르고 끝난다는것이다. 낮, 밤 오르락 내리락 하다가 결국 +1일차인 다음날 낮에 정상에 도달한다는 것이다.
이를 수식으로 써보면 (낮-밤) x n번 + 낮 >= 정상높이 가 된다.
그래서 구해야 할 일 수는 낮과 밤이 반복된 N일차 + 정상에 도달한 다음날 낮 해서 N+1이 된다.
따라서 최종적으로 식을 정리하면 n+1 = (V-A) / (A-B) 이 된다.
문제해결
> 낮에 이동거리 A, 밤에 미끄러지는 거리 B, 최종 목표 V를 입력받는다.
> 앞서 구한 수식으로 일자를 정의해준다.
> 이때, 나누기 연산의 결과가 실수로 나올 경우가 있다.
n.xxx.. 는 n일 보다 더 크다는 뜻이므로 이 경우엔 추가로 1일을 더 해준다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main
{
//2869번 달팽이는 올라가고 싶다
static int A, B, V;
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
V = Integer.parseInt(st.nextToken());
int days = (V - A) / (A - B) + 1;
if((V - A) % (A - B) != 0) days += 1;
System.out.println(days);
}
}
후기
처음에 반복문으로 낮 더하고, 밤 빼고를 반복하며 V보다 크거나 같아지면 해당 일 수를 출력하도록 했다. 시간초과가 나버렸다.
주어진 조건을 보니 0.25초에 해결하라고 한다. 1초가 대략 1e8인데 V가 1,000,000,000까지이므로 최악의 경우 1e9까지 나와 시간초과가 난다.
이런 문제는 보통 점화식을 세우거나 뭔가 방법이 있는 문제이다. 따라서 어떻게 하면 일자를 구할 수 있을 지 수식으로 정리하여 생각했더니 풀렸다.
