[백준 알고리즘 C/C++] 1011번 문제 풀이: Fly me to the Alpha Centauri

** 이 글을 읽음에 앞서 포스팅 된 소스가 100% 정답은 아님을 밝힙니다.

    더욱 유능한 분께서 클린 / 최적의 소스를 짜셨을 가능성이 높습니다.

    기록용으로 남기며, 참고만 부탁드립니다.

** 백준 알고리즘은 직접 풀이를 해보시는 것을 권장합니다.

---

● 문제

난이도[티어] : 골드 5

백준 알고리즘 1011번 Fly me to the Alpha Centauri

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

1011번: Fly me to the Alpha Centauri

---

● 풀이 방법

우주선은 점차 증가했다가 일정 지점에서 부터 감소하는 것을 인지하고 있어야 한다.

출발지점에서 1씩 증가하다가 도착할 때 1로 도착한다는 말이 적혀 있기 때문.

나는 대칭 구조를 찾아내어 연산하는 것으로 소스를 작성 했다.

대칭구조를 찾을 때 속도의 경우는 아래와 같은 4개의 케이스로 나오게 된다.

 

CASE 1 : 완벽한 대칭 구조 [ ex) 거리 20  ->  1 2 3 4 4 3 2 1 ]

 

CASE 2 : 고점이 하나인 대칭 구조  [ ex) 거리 16  ->  1 2 3 4 3 2 1 ]

 

CASE 3 : 일부 지점에서 속도가 유지되는 경우 [ ex) 거리 18  ->  1 2 3 4 3 2 2 1 ]

 

CASE 4 : 고점이 없는 경우 ( 즉 1인 경우 )  [ ex) 거리 3  ->  1 1 1 ]

---

● 소스 코드

#include <stdio.h>
#include <iostream>

int main(void)
{
    //baekjoon No.1011
    int X; // 출발위치
    int Y; // 목표위치
    int Test_case; // 테스트 횟수 
    int dest; // x와y의 거리
    int total_dest;
    int total_move_cnt;
    int i = 1;

    std::cin >> Test_case;
    for(int a = 0; a < Test_case; a++){
        i = 1;
        total_move_cnt = 0;
        total_dest = 0;
        std::cin >> X;
        std::cin >> Y;
        dest = Y - X; 
        while(1)
        {
            if(dest-total_dest == i*2){
                //완벽한 대칭 (이동횟수 : 짝수)
                total_move_cnt = i*2;
                break;
            }else if(dest-total_dest < i*2){
                //더 이상 대칭 구조를 찾지 못할 때,
                if(i>=dest-total_dest){
                    //마지막 남은 숫자가 대칭 값 최고값이거나 낮을 때,
                    total_move_cnt = ((i-1)*2) + 1;
                }else{
                    total_move_cnt = ((i-1)*2) + 2;
                }
                break;
            }else{
                //대칭 숫자들 중 가장 높은 숫자를 구하지 못했을 때,
                total_dest = total_dest+(i*2);
            }
            i++;
        }
        printf("%d\n",total_move_cnt);
    }
}

 

우선적으로 완벽한 대칭구조가 존재 한지 여부 부터 확인 [ CASE 1 ]

대칭 구조를 찾지 못했으나 고점을 찾았을 때. [ CASE 2 / 3 ]

대칭 숫자들 중 가장 높은 숫자를 찾지 못했을 때. [ CASE 4 ]

로 구분지어서 결과를 도출해 내었다.

 

---

● 결과

** 코드 길이가 상이 할 수 있습니다! 그러나 내용물은 같습니다.

    이유)  주석 및 더미 소스 유무