[백준] 1669 멍멍이 쓰다듬기

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

1669번: 멍멍이 쓰다듬기

🥈실버이지만 그렇다고 쉽지만은 않았던 문제였다.

우선 무턱대고 푸는 것이 아니라 규칙이 있나부터 살펴봐야했다.

문제에서 처음과 마지막에는 반드시 1cm만 클 수 있다고 했고, 1cm씩만 조정가능하다고 했기 때문에

n일 간 성장할 수 있는 최대 길이가 마치 정규분포를 그리듯 대칭적으로 규칙을 가지고 있다.

 

날짜 수	최대 성장 가능한 패턴
3	1 2 1
4	1 2 2 1
5	1 2 3 2 1
6	1 2 3 3 2 1
7	1 2 3 4 3 2 1
8	1 2 3 4 4 3 2 1

이를 간단한 수학 공식을 써서 공식화하였다.

2n일에는 최대 n(n+1)만큼 성장하고, 2n + 1일에는 최대 (n+1)^2만큼 성장(n >= 0)

 

만약 정수의 해가 나오지 않는다면 날짜를 올림 처리하여서 최소 소요 기간을 O(1)만으로 파악할 수 있다.

이렇게 해도 통과가 되지 않았어서 당황했는데 역시나 이번에도 Overflow를 간과했었다.

예를 들어 41707 2147483647를 입력하면 상당히 키 차이가 많이 나게 된다.

여기에다가 근의 공식을 적용하는 과정에서 4를 곱하면 오버 플로우가 발생했다.

이로 인해 음수 처리되면서 루트 안에 음수? 바로 Nan 처리 됐다.

이를 방지하기 위해 자료형을 int에서 long long으로 바꾸었다.

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int dog, monkey;
    cin >> dog >> monkey;
    // LL For Prevent Overflow!
    long long diff = monkey - dog;

    float day1 = (-1 + sqrt(1 + 4 * diff)) / 2;
    if(day1 == floor(day1)) {
        cout << day1  * 2 << endl;
        return 0;
    }

    float day2 = sqrt(diff) - 1;
    if(day2 == floor(day2)) {
        cout << day2 * 2 + 1 << endl;
        return 0;
    }

    if(ceil(day1) == ceil(day2)) {
        cout << 2 * ceil(day2) << endl;
    } else {
        cout << 2 * ceil(day2) + 1 << endl;
    }
    return 0;
}