백준-일반 수학 1 2869 달팽이는 올라가고 싶다.

달팽이는 올라가고 싶다 

낮에는 올라가고 밤에는 일정 거리만큼 미끄러진다.

목표지점에 도달하면 다시는 미끄러지지 않는다. 

목표까지 도달하는 기간을 구하시오.

제약사항

• 0 < B <= A= V <= 1,000,000,000

주의 사항

반복문 쓰면 시간제약에 무조건 걸린다. 한번의 연산으로 해결해야 한다. 계산식은 다음과 같이 도출된다.

마지막날은 올라가고 미끄러지지 않는다 == 높이 - (미끄러지는 거리) / 실제로 이동한 거리, 나머지가 나오면 그것은 하루가 추가되는 것이다.

C풀이

달팽이는 올라가고 싶다_2869.c

/*
처음에 작성한 반복연산 코드 
시간초과가 발생
==> 알고리즘의 변경이 필요함
===> 뺄셈연산이 아닌 나눗셈 연산으로 전환
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main() {
    int V, A, B, result = 0, i;
    
    scanf("%d %d %d", &A, &B, &V);

    for (i = 1; result <= V; i++) {
        result += A;
        if (result < V)
            result -= B;
        else
            break;
    }
    printf("%d", i);
    return 0;
}
*/
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main() {
    int V, A, B, result;
    
    scanf("%d %d %d", &A, &B, &V);
    //  미끄러지지 않을 거리 - 나머지 발생시키기 / 실제 올라간 거리, 1일은 무조건 올라가기만함
    result = (V - B - 1) / (A - B) + 1; 
    printf("%d\n", result);
    return 0;
}

C++풀이

달팽이는 올라가고 싶다_2869.cpp

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main() {
    int x, i; // x는 분자, i는 분모
    //분모는 0이 아니니까 항상 1부터 시작한다.
    // 그런데 왜 분모 / 2가 0일 때 항상 진행방향이 DOWN이냐??????
    scanf("%d", &x);	

    for (i = 1; x > i; i++) {
        x -= i;
    }
    if (i % 2 == 0) {
        printf("%d/%d\n", x, i - x + 1);
    }
    else {
        printf("%d/%d\n", i - x + 1, x);
    }

    return 0;
}

모든 예제 코드의 소스파일은 제 개인 깃허브 레포지토리 에 있습니다.

Workspace/알고리듬 풀이 at main · cyphen156/Workspace · GitHub

Workspace/알고리듬 풀이 at main · cyphen156/Workspace