[C++] 백준 1669번 멍멍이 쓰다듬기

원숭이가 강아지보다 키가 커질때까지 몇일이 걸리는지 구하는 문제입니다.

 

원숭이의 키는 그전날에 컸던 키의 -1, 0, +1 cm가 클 수 있습니다.

첫날에는 1cm로 시작하며

마지막날에는 1cm로 끝나야 합니다.

 

ex) 11cm - 6일

1day	2day	3day	4day	5day	6day	7day	8day	9day	10day
1	2	3	2	2	1	X	X	X	X

ex) 30cm - 10일

1day	2day	3day	4day	5day	6day	7day	8day	9day	10day
1	2	3	4	5	5	4	3	2	1

ex) 16cm - 7일

1day	2day	3day	4day	5day	6day	7day	8day	9day	10day
1	2	3	4	3	2	1	X	X	X

 

1. n*n은 n*2-1(일)입니다.

    1*1 = 1*2-1(1일)

    2*2 = 2*2-1(3일)

    3*3 = 3*2-1(5일)

    4*4 = 4*2-1(7일)

 

2. n*n-n은 n*2-2(일)입니다.

    1*1-1 = 1*2-2(0일)

    2*2-2 = 2*2-2(2일)

    3*3-3 = 3*2-2(4일)

    4*4-4 = 4*2-2(6일)

 

1번과 2번은 각각 n일 일때 최대 값입니다.

1) n*n-n < x <= n*n = n*2-1일

2) n*n-n > x = n*2-2일

 

처음 숫자 1부터 반복해서 n의 제곱을 구하고 만약 키차이가 n보다 작으면

n*n-n 보다 큰지 확인을 하고 크면 n*n-1일을 출력

n*n-n 보다 작거나 같으면 n*n-2일을 출력

 

#include  
using namespace std; 

int main(int argc, char *argv[]) 
{ 
    unsigned int count = 0;     // 1씩 증가하면서 제곱값 확인
    unsigned int monkey, dog;     // 원숭이, 강아지 키
    unsigned int key;     // 강아지 - 원숭이 키
    count = 0; 
    cin >> monkey >> dog; 
    key = dog - monkey; 
    if (key < 1) {     // 키차이가 1보다 작은 경우
        cout << 0; 
        return 0; 
    } 
    while (count * count < key) {     // 제곱값이 키차이값 보다 작으면 반복
        ++count; 
    } 
    if (count * count - count < key) {     // 설명 참고
        cout << count * 2 - 1; 
    }     
    else { 
        cout << count * 2 - 2;     // 설명 참고
    } 
    return 0; 
}