lango

찍먹? 부먹?
난 부먹 개발자.

1 minute read



입출력예제

Input-1
2 1 5
Output-1
4

Input-2
5 1 6
Output-2
2

Input-3
100 99 1000000000
Output-3
999999901


문제 풀이

낮에 A미터를 이동하고 밤에 B미터가 미끄러지며 V미터에 도달하는데 걸리는 일수를 구해야 한다.

먼저 단순한 반복문을 활용해 코드를 작성하였다.
up에 A를 더하고 B를 빼가며 목표 V에 도달했을 때의 날짜수(day)를 구하도록 하였다.

1
2
3
4
5
6
7
8

int up = 0;
int day = 0;
while(true) {
    up += A;
    day++;
    if(up >= V) break;
    if(up<V) up -= B;            
}

그런데, 이 문제는 0.15초의 시간제한이 걸려있다.
그렇기에 단순한 반복문으로 접근하게 되면 시간초과가 발생한다.

시간초과 해결

주어진 예제대로 A를 2, B를 1, V를 5라고 해보자.

  • 1일차: (A-B) = (2-1) = 1
  • 2일차: (A-B)+(A-B) = (2-1)+(2-1) = 2
  • 3일차: (A-B)+(A-B)+(A-B) = (2-1)+(2-1)+(2-1) = 3
  • 4일차: (A-B)+(A-B)+(A-B)+A = (2-1)+(2-1)+(2-1)+2 = 5

위 식대로 정상에 도달하게 되면 미끄러지지 않기 때문에 4일차 낮에 목표 V에 도달할 수 있다.
그렇다면 일자별로 낮 연산만 수행하여 V에 도달할 떄의 날짜(N)는지를 검증할 수 있다.

  • D일차 낮: (A-B) * (D-1) + A
  • V = AD - A - BD + B + A
  • V = D(A-B) + B
  • V - B = D(A-B)
  • D = (V-B) / (A-B)

위 식대로 예제에 적용해보자.

1
2

// A=2, B=1, V=5
D = (5-1) / (2-1) = 4/1 = 4

위와 같이 V에 도달하기까지 걸리는 일수를 구할 수 있다.

1
2
3

// A=3, B=1, V=8
D = (8-1) / (3-1) = 7/2 = 3.5
//소수점 올림하여 D는 4

D값이 소수점이 나왔을 경우에는 하루를 더 이동해야 한다는 것(소수점만큼 더 이동해야 한다는 것)이므로 소수점 올림을 해주어야 한다.

이제 위 내용들을 통해 정리된 식을 코드로 작성해보자.

1

int D = (int) Math.ceil((double)(V-B) / (A-B));

Math.ceil() 메서드를 통해 소수점 올림을 해주었다.


작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        int D = (int) Math.ceil((double)(V-B) / (A-B));
        bw.write(Integer.toString(day));
        
        bw.flush();
        bw.close();
        br.close();
    }
}

회고

  • 목표 V미터에 도달하기까지 걸리는 일수(D)를 구하기 위한 식을 낮과 밤을 모두 고려하려고 하다보니 복잡했지만, 정상에 도달했다면 미끄러지지 않는다는 점을 통해 일자별 낮 연산만을 고려하여 식을 도출하였다.
  • 수학적 사고가 요구되어 수학 공부의 필요성을 느꼈다..

You may also enjoy