[BOJ] 백준 1011 Fly me to the Alpha Centauri

* 변수 오버플로우를 잘 고려하자!!!

이미지를 클릭하면 문제 사이트로 이동합니다.

---

💣 문제 이해

 

약간의 수학적인 규칙을 찾는 것이 필요한 문제였다. 첫 번째는 무조건 1 만큼 이동, 이후로는 다음과 같은 규칙이 있다.

이전에 1 만큼 움직였다면 이번에는 0, 1, 2 중 선택해서 이동이 가능하다.

이전에 2 만큼 움직였다면 이번에는 1, 2, 3 중 선택해서 이동이 가능하다.

거리를 입력받았을 때, 이 규칙 내에서 처음 지점에서 끝 지점까지 정확하게 도착할 수 있는 최소 이동 횟수를 구하여 출력하면 된다.

 

 

💭 풀이 과정

 

이동거리를 1부터 차례대로 적어가며 규칙을 찾아보았다.

 

이동 거리	이동 방식	이동 횟수
1	1	1
2	1  1	2
3	1  1  1	3
4	1  2  1	3
5	1  2  1  1	4
6	1  2  2  1	4
7	1  2  2  1  1	5
8	1  2  2  2  1	5
9	1  2  3  2  1	5
10	1  2  3  2  1  1	6
11	1  2  3  2  2  1	6
12	1  2  3  3  2  1	6
13	1  2  3  3  2  1  1	7
14	1  2  3  3  2  2  1	7
15	1  2  3  3  3  2  1	7
16	1  2  3  4  3  2  1	7

 

다음과 같은 규칙으로 코드를 작성했다.

 

1. 입력에서 구한 이동거리(dist) 보다 큰 제곱 수를 찾는다.(i * i)

2. 만약 dist가 이전 제곱 값인 (i-1)*(i-1)이면 이동 횟수는 2*i-3 이다.

3. 만약 dist가 이전 제곱 값은 아니지만, 그 중간 값(end-i+1)보다 작다면 이동 횟수는 2*i-2 이다.

4. 만약 dist가 중간 값보다 크고 i*i보다 작다면 이동 횟수는 2*i-1 이다.

 

이를 바탕으로 처음에 작성한 소스이다. (이번에도 시간 초과;;;)

작성 언어: C++

 

#include <cstdio>
int main(){
    int cycle, x, y, dist = 0, i = 1;
    scanf("%d", &cycle);
    while(cycle--){
        scanf("%d %d", &x, &y);
        dist = y - x;
        while(1){
            if(i * i > dist)   break;
            ++i;
        }
        int fnt = (i-1)*(i-1)+1;
        int end = i*i;
        if(dist == fnt-1)
            printf("%d\n", 2*i-3);
        else if(dist < end-i+1)
            printf("%d\n", 2*i-2);
        else
            printf("%d\n", 2*i-1);
        i = 1;
    }
    return 0;
}

 

이상하게 문제에 나와있는 입력 값으로는 정확하게 값이 출력되는데, 제출하면 시간초과가 뜬다;; (또간초과..)

그리 난이도가 높은 문제가 아닌데 진짜 저 while 부분이 문제인가 해서 생각할 수 있는 온갖 다양한 방법은 다 해보았다.

근데 결과는 계속 시간초과;;;;

 

 

 

수정하여 작성한 소스이다.

작성 언어: C++

 

#include <cstdio>
int main(){
    long cycle, x, y, dist = 0, i = 1;
    scanf("%ld", &cycle);
    while(cycle--){
        scanf("%ld %ld", &x, &y);
        dist = y - x;
        while(1){
            if(i * i > dist)   break;
            ++i;
        }
        long fnt = (i-1)*(i-1)+1;
        long end = i*i;
        if(dist == fnt-1)
            printf("%ld\n", 2*i-3);
        else if(dist < end-i+1)
            printf("%ld\n", 2*i-2);
        else
            printf("%ld\n", 2*i-1);
        i = 1;
    }
    return 0;
}

 

문제는 생각보다 복잡한 데에 있지 않았다. 바로 <정수 범위 오버플로우> 때문이었다.

int 변수는 4바이트, 범위는 -2,147,483,648 ~ 2,147,483,647 ( -2³¹ ~ 2³¹ - 1 ) 이다.

 

i * i > dist 에서 i 는 제곱하면 dist보다 큰 값을 찾는 것이다.

문제의 조건은 x < y < 2³¹ 인데, 만약 y가 정수 최대 범위인 2³¹ - 1 이고 x가 0, 1, 2 등 과 같이 작은 수라면 dist 또한 정수 최대 숫자인 2,147,483,647에 가깝다.

그 말인즉슨, i * i 가 정수 최대 범위를 벗어나서 (오버플로우) 음수가 된다는 말이다. 오우......

while 문도 영영 벗어나지 못할 수도 있고, end 변수도 int라면 음수가 되어서 올바른 값이 나오지 않게 된다.

 

int를 더 넓은 범위인 long으로 바꾸니 문제 해결..!!

 

 

🏆 배운 점

 

변수 범위가 좀 위험하게 크다 싶으면 그냥 묻고 long으로 가자.