[C]백준 2869번 : 달팽이는 올라가고 싶다

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

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

시간제한이 0.15초! 이전의 손익분기점 문제가 떠오르는 조건이다.

비슷하다면 비슷할 수 있는 문제이니 참고할 분이 계시다면

https://www.acmicpc.net/problem/1712

1712번: 손익분기점

즉 반복문을 사용하지 말라는 것.

그렇다면 식을 구성해봐야겠다가 최우선적으로 머리에 스친다.

가장 중요한 조건은 " 정상에 올라간 후에는 미끄러지지 않는다."

조건을 고려하지 않고 식을 세워봤다.(A-B)*x>= V 일 때의 x의 최솟값이 우리가 원하는 값일 것 그렇다면 여기서 조건을 섞어본다면?

(A-B)*(x-1)+A >=V

우리가 원하는 x값을 뽑아오기 위하여 정리해보자.

x >= (V-A)/(A-B) + 1

'/'연산 시에는 항상 고려해줘야 할 것

나눗셈 연산을 수행하기 때문에 소수점이 있었을 수 있다.

우리는 위 부등식을 코드로 구현하기 위해 등식으로 나타낼 것인데

그 과정에서 부등식의 성질이 누락될 수 있다.

예) x >= 1.xx 라면 x는 2여야하는데 코드에서는 소수점을 절삭하고 등식이므로 x == 1이 된다.

따라서 만약 연산결과에 소수점이 있었다면 +1을 해줘야한다.

이 과정을 코드로 나타내면

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

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

    if ((V - A) % (A - B) == 0) x = (V - A) / (A - B) + 1;
    else x = (V - A) / (A - B) + 2;

    printf("%d", x);

    return 0;
}

반복문으로 쉽게 풀린다고 우당탕탕 반복문을 쓸 게 아니라 식으로 구현할 수 있는지 묻는 문제였다.

수학 관련 문제는 유독 더 어려운 것 같다..

 

☞ 다른 사람의 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {
    int A, B, V;
    int day;
    scanf("%d%d%d",&A,&B,&V);

    day = (V - B - 1) / (A - B) + 1;

    printf("%d", day);

    return 0;
}
출처 : https://yahohococo.tistory.com/28

소수 일 때 케이스 분류하기 귀찮으니 그냥 (V - B)에서 1을 빼버렸다.

흠 내 머리로는 이해가 어렵다..