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

수학, 211027

문제

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

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

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

입력

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

출력

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

예제 입력 1

Plain Text
복사

예제 출력 1

Plain Text
복사

예제 입력 2

Plain Text
복사

예제 출력 2

Plain Text
복사

예제 입력 3

Plain Text
복사

예제 출력 3

Plain Text
복사

my solution

올라갈 때마다 1일씩 증가된다. 그리고 V인지 검사한다. V이면 day를 출력한다. V가 아니면 B만큼 h를 줄여준다.

function solution(i) {
    let answer = 0;
    const input = i
        .toString()
        .trim()
        .split(" ")
        .map((v) => parseInt(v));
    [A, B, V] = input;
    let h = 0;

    while (1) {
        h += A;
        answer++;
        if (h >= V) {
            // answer = answer.toString();
            return answer.toString();
        } else h -= B;
    }
}

test("solution", () => {
    expect(solution("2 1 5")).toStrictEqual("4");
    expect(solution("5 1 6")).toStrictEqual("2");
    // expect(solution("100 99 1000000000")).toStrictEqual("999999901");
});
JavaScript
복사

처음에는 이렇게 풀었는데 마지막 테스트케이스 숫자도 매우 크고 시간 제한이 걸려있는 걸로 봐서 수학적으로 단축시킬 수 있는 방법을 찾아야 할 것 같았다.

V가 주어지면 매일매일이 지날 때마다 하루에 A-B미터만큼 이동할 수 있으니 마지막에 V에 도달할 때 낮에 도착하는 것을 가정해보았다.

이렇게 되려면 V에서 A를 뺀 값을 A-B로 나누어서 몫이 이전까지 걸린 일수이고 마지막으로 A를 더해줬으니 하루를 더 더해주는 것이다.

1번 TC를 보면 2 1 5인데 위의 공식에 따르면 5-2를해서 3이 되고 A-B = 1이므로 3을 나눴을 때 3일이 된다.

따라서 3일 + 1일(낮)을 해서 4일이 답이 된다.

2번 TC를 보면 5 1 6인데 위의 공식에 따르면 6-5를 해서 1이 된다. 5-1은 4이므로 1을 나눴을 때 1일이 된다.

따라서 1일 + 1일(낮)을 해서 2일이 답이 된다.

3번 TC를 보면 100 99 1000000000 인데 위의 공식에 따르면 999999900이 된다. 100-99는 1이므로 앞의 숫자를 나눴을 때 999999900일이 된다. 따라서 999999900일 + 1일(낮)을 해서 999999901일이 된다.

// 이렇게 되려면 V에서 A를 뺀 값을 A-B로 나누어서 몫이 이전까지 걸린 일수이고 마지막으로 A를 더해줬으니 하루를 더 더해주는 것이다.
// 예시) 1번 TC를 보면 2 1 5인데 위의 공식에 따르면 5-2를해서 3이 되고 A-B = 1이므로 3을 나눴을 때 3일이 된다.
// 따라서 3일 + 1일(낮)을 해서 4일이 답이 된다.
function solution(i) {
    const input = i
        .toString()
        .trim()
        .split(" ")
        .map((v) => parseInt(v));
    [A, B, V] = input;
    let h = V - A;
    const lastDay = A - B;
    let day = h / lastDay >= 1 ? Math.round(h / lastDay) : h % lastDay;

    console.log(day + 1);
JavaScript
복사

이렇게 하니까 70%정도에서 fail이 나왔다.

분명히 이게 최적의 해 같았는데 안되는 것을 보고 입력 조건을 다시 보았다.

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

V와 A가 같아지는 경우가 있을 수 있음을 알 수 있었다.

근데 이 경우 h = V - A = 0이 되버리면서 0 / lastDay로 day의 삼항연산자가 false가 되고 h % lastDay의 값이 들어가게 된다.

하지만 이 값이 들어가면 A-B가 들어가는 것이다. A만 해도 도착하는 것이 맞기 때문에 잘못된 계산이므로

에지케이스처리를 아래와 같이 추가해줬더니 통과되었다.

소스코드

// & : 반례 : V가 A보다 같거나 작을수가 있다. 1번에 올라가는 것을 처리해주는 조건문을 넣어주자.
function solution(i) {
    const input = i
        .toString()
        .trim()
        .split(" ")
        .map((v) => parseInt(v));
    [A, B, V] = input;
    let h = V - A;
    const lastDay = A - B;

    let day =
        Math.ceil(h / lastDay) >= 1 ? Math.ceil(h / lastDay) : h % lastDay;

    if (A >= V) day = 0;
    console.log(day + 1);
    return (day + 1).toString();
}

test("solution", () => {
    expect(solution("2 1 5")).toStrictEqual("4");
    expect(solution("5 1 6")).toStrictEqual("2");
    expect(solution("100 99 1000000000")).toStrictEqual("999999901");
});
JavaScript
복사