[C/C++] 백준 #1669 멍멍이 쓰다듬기(수학)

멍멍이 쓰다듬기 문제는 1부터 n까지의 합을 계산하는 것을 응용합니다.

 

puppy and monkey

 

첫째날과 마지막날은 1cm가 되어야 하고, 매일 조절할 수 있는 양이 1cm이므로, 10cm를 늘려야 한다면, 1cm, 2cm, 3cm, 2cm, 1cm, 1cm 형태가 되어야 합니다.

 

늘려야 하는 양이 y cm라고 했을 때, x는 최대값이 됩니다.  즉, 10cm를 늘려야 한다면, 1cm, 2cm, 2cm, 1cm 형태로 늘리는 형태입니다.  그러면 총 6cm 길이가 되고, 남은 길이는 4cm가 됩니다.  그러면 x+1만큼을 제하면, 1cm가 남습니다.  그러면 그 값은 이제까지 나왔던 값 중에 반드시 하나가 됩니다.

 

일단 다음과 같은 식을 이용해서 우리는 x값을 구합니다.

\[ x^2 + x \le y \]

\[ x \le \frac{-1 + \sqrt{1 + 4y}}{2} \]

그리고 남은 값을 찾아보고, 남은 값이 0인 경우에는 \(2x\), 남은 값이 \(x+1\)보다 작거나 값으면 \(2x+1\), 그렇지 않으면 \(2x+2\)가 됩니다.

 

10cm라면, 총 6일이 걸리는데, 위와 같이 하면, x의 최대 정수값은 2가 됩니다.  남은값은 4가 되므로, 이 값은 3보다 큰 값이므로, 6일이 됩니다.

15cm라면, 총 7일이 걸리는데, x의 최대 정수값은 3이 됩니다.  남은 값은 3이 되고, 이 값은 4보다 작은 값이므로 7일이 됩니다.

 

글을 쓰면서 생각한 것은 차라리 제곱근을 구해서 가장 큰수보다 큰 경우를 따지는 것이 좋을 듯 합니다.  10cm라면, 10의 제곱근보다 작거나 같은 최대 정수는 3이고, 제곱해서 뺀수는 1이므로, 6일.  15cm라면, 최대 정수는 3이 되고, 제곱해서 뺀수는 6이 되므로 2일을 더해서 7일이 되는 식으로 계산하는 것이 더 편할 듯 합니다.

 

아래는 제가 작성한 소스입니다.  고칠 곳이 보이긴 합니다.  소스는 참고용으로만 봐주세요.

//----------------------------------------------------------
//    baekjoon #1669 - Patting a Puppy
//        - by Aubrey Choi
//        - created at 2020-02-28
//----------------------------------------------------------
#include <stdio.h>
#include <math.h>
int main()
{
    int a, b, c=0;
    scanf("%d%d", &a, &b);
    b -= a;
    c = (-0.999999+sqrt(1+4.0*b))/2.0;
    b -= c*(c+1);
    if(b > 0) { b -= c+1; c = c*2+1; } else c = c*2;
    if(b > 0) c++;
    printf("%d\n", c);
}