백준 알고리즘 1011번: Fly me to the Alpha Centauri C언어

문제 출처 : https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

1. 코드

#include <stdio.h>

void Ptr(int a)
{
    long i, j, cnt;
    
    i = j = 2;
    cnt = 0;
    
    if(a == 1 || a == 2)
    {
        printf("%d\n", (a == 1) ? 1 : 2);
        return 0;
    }
    
    while(1)
    {
    	if(cnt == 2)
        {
            i++;
            cnt = 0;
        }
        j += i;
        cnt++;
        if(j >= a)
            break;
    }
    printf("%ld\n", (cnt==1) ? i*2-1 : i*2);
}

int main(void)
{
    int t, x, y, i;
    
    scanf("%d", &t);
    
    for(i = 0; i < t; i++)
    {
        scanf("%d %d", &x, &y);
        Ptr(y - x);
    }
    return 0;
}

 

2. 문제 해결 방식

우선 이 문제의 범위가 상당히 크기 때문에 시간 초과 에러가 발생하기 매우 쉽다. 그런데 한번 예제를 나열해보자.

거리	최소 이동 횟수
1	1
2	2
3	3
4	3
5	4
6	4
7	5
8	5
9	5
10	6
11	6
12	6

예제를 표로 정리한 것인데 표를 자세히 살펴보자

최소 이동 횟수가 3인 거리가 3, 4이고 4인 거리는 5, 6 그리고 5인 거리는 7~9, 6인 거리는 10~12까지이다. 여기서 2인 크기만큼 두 번 묶이고 3인 크기만큼 두 번 묶인다. 그 말은 즉, 다음은 4인 크기가 5인 크기가 9999인 크기가 2번씩 묶이다는 소리이다.

그리고 조그만 더 생각을 확장시켜보면 0부터 9999까지 1씩 더하는 방식보다는 이렇게 수를 늘려가면서 더하는 방식이 더 빠른 속도를 낸다. 아마 이것으로 시간 초과 에러는 해결될 것이다. 그리고 또 하나의 규칙을 발견해야 하는데 그 규칙은 다시 표를 살펴보면 된다.

파란색과 빨간색 그림을 보고 하나의 공식을 발견하면 된다. 먼저 파란색 1번과 2번을 보면 1번은 3이고 2번은 4이다. 그리고 3번을 보고 한번 공식을 만들어보자

사람마다 다르겠지만 나는 여기서 1번은 2 × 2 - 1을 2번을 보고 2 × 2를 떠올렸다. 그리고 그것을 빨간색도 마찬가지로 3번을 보고 3 × 2 - 1 그리고 4번은 3 × 2를 떠올렸다. 그렇다면 이 식을 공식화 한다면 1번과 3번은 A × 2 - 1이고 2번과 4번은 A × 2이다. (이때 A는 임의 수이다.)

마지막으로 자료형을 int 형으로 선언한다면 오버플로우가 생겨서 정확한 값을 구할 수 없기 때문에 int 형보다 큰 long 형을 쓰는 것을 추천한다.

 

3. 느낀 점

이 문제는 정말 힘들었다. 특히 시간 초과 에러가 나를 미친 듯이 괴롭혔다. 3일 정도 걸렸지만 풀어낸 것에 대해 만족한다. 그리고 처음으로 '틀렸습니다' 에러가 나왔을 때 정말 기뻤다. 왜냐하면 '틀렸습니다' 에러가 나왔다는 것은 시간 초과 에러는 해결했다는 의미이기 때문이다.

솔직히 3일째 되는 날에도 포기할 뻔했지만 에러가 시간 초과가 아닌 '틀렸습니다' 에러여서 마지막까지 포기할 수 없었던 것 같다. 그리고 이 문제를 푸는데 많은 도움을 받은 질문 글을 올리겠다. 참고로 이 글은 코드를 보여주거나 힌트를 주는 것이 아닌 예제를 알려주는 것이기에 편한 마음으로 봐도 무방할 것이다.

도움받은 질문 : https://www.acmicpc.net/board/view/26059

글 읽기 - ★★★ 필독!!! ★★★ Fly Me FAQ ★★★ 안 읽으면 후회! ★★★