[C] Fly me to the Alpha Centauri

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

1011번: Fly me to the Alpha Centauri

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행

www.acmicpc.net

1. 1. 문제

1.1. 💡 문제

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다.

그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다. 예를 들어, 이 장치를 처음 작동시킬 경우 -1 , 0 , 1 광년을 이론상 이동할 수 있으나 사실상 음수 혹은 0 거리만큼의 이동은 의미가 없으므로 1 광년을 이동할 수 있으며, 그 다음에는 0 , 1 , 2 광년을 이동할 수 있는 것이다. ( 여기서 다시 2광년을 이동한다면 다음 시기엔 1, 2, 3 광년을 이동할 수 있다. )

김우현은 공간이동 장치 작동시의 에너지 소모가 크다는 점을 잘 알고 있기 때문에 x지점에서 y지점을 향해 최소한의 작동 횟수로 이동하려 한다. 하지만 y지점에 도착해서도 공간 이동장치의 안전성을 위하여 y지점에 도착하기 바로 직전의 이동거리는 반드시 1광년으로 하려 한다.

김우현을 위해 x지점부터 정확히 y지점으로 이동하는데 필요한 공간 이동 장치 작동 횟수의 최솟값을 구하는 프로그램을 작성하라.

1.2. 💡입력

입력의 첫 줄에는 테스트케이스의 개수 T가 주어진다. 각각의 테스트 케이스에 대해 현재 위치 x 와 목표 위치 y 가 정수로 주어지며, x는 항상 y보다 작은 값을 갖는다. (0 ≤ x < y < 2^31)

1.3. 💡 출력

각 테스트 케이스에 대해 x지점으로부터 y지점까지 정확히 도달하는데 필요한 최소한의 공간이동 장치 작동 횟수를 출력한다.

2. 2. 풀이


      
      
      
    
    
      <c++ />
    
#include <stdio.h>
#include <math.h>

int activate_Machine(int, int);

int main(){
    int i, x_Val, y_Val;
    int testCase = 0;

    scanf("%d", &testCase);
    
    for (i = 0 ; i < testCase ; i++){
        x_Val = y_Val = 0;
        scanf("%d %d", &x_Val, &y_Val);
        
        printf("%d\n", activate_Machine(x_Val, y_Val));
    }
}

int activate_Machine(x_Val, y_Val){
    int x2y_Distance, jump_Count, sqrt_Value, pow_Value;
    
    jump_Count = sqrt_Value = pow_Value = 0;
    x2y_Distance = y_Val - x_Val;

    if (x2y_Distance <= 3){
        switch (x2y_Distance)
        {
        case 1:
            jump_Count = 1;
            break;
        case 2:
            jump_Count = 2;
            break;
        case 3:
            jump_Count = 3;
            break;
        }
    }
    else{
        sqrt_Value = floor(sqrt(x2y_Distance));
        pow_Value = pow(sqrt_Value, 2.0);

        if (pow_Value >= x2y_Distance){
            jump_Count = sqrt_Value * 2 - 1;
        }
        else if (pow_Value < x2y_Distance && x2y_Distance <= (sqrt_Value + pow_Value)){
            jump_Count = sqrt_Value * 2;
        }
        else if (x2y_Distance > (sqrt_Value + pow_Value)){
            jump_Count = sqrt_Value * 2 + 1;
        }
    }

    return jump_Count;
}

3. 3. 메모

수포자인 내게는 굉장히 까다로운 문제였다. 문제를 잘못 이해하여 k, k + 1 광년 이동한다 가정하고 풀었는데 알고 보니 최대치 광년 이동을 한 직후 다시 k, k - 1 광년씩 내려와 마지막 1 광년 이동할 수 있도록 해야 했다.

처음과 끝은 1광년으로 고정되어 있으니, 그것을 감안하고 규칙을 찾아가면 된다. 일종의 패턴을 찾는 문제이다. 패턴을 찾기 위해 이것저것 시도해보다가 한 가지 아이디어가 떠올랐다. y_Value 값에서 x_Value 값을 빼주면 x 좌표부터 y 좌표까지의 거리가 나온다. 변수 x2y_Distance를 하나 만들어 그 값을 담아 두고, 공간 이동 장치 값에 위배되지 않는 선에서 최소한으로 점프를 했을 때의 값을 하나하나 구했다.

x2y_Distance	jump_Count	x2y_Distance	jump_Count
1	1	16	7
2	2	17	8
3	3	18	8
4	3	19	8
5	4	20	8
6	4	21	9
7	5	22	9
8	5	23	9
9	5	24	9
10	6	25	9
11	6	26	10
12	6	27	10
13	7	28	10
14	7	29	10
15	7	30	10

이렇게 놓고 보니 규칙이 조금 보이는 것 같다. x2y_Distance 값이 1, 2일 때를 제외하면 / 3 - 3, 4 - 4 /, / 5 - 5 - 5, 6 - 6 - 6 /, / 7 - 7 - 7 - 7, 8 - 8 - 8 - 8/, ... 로 나열되어 있다.

x2y_Distance	jump_Count	x2y_Distance	jump_Count
1	1	16	7
2	2	17	8
3	3	18	8
4	3	19	8
5	4	20	8
6	4	21	9
7	5	22	9
8	5	23	9
9	5	24	9
10	6	25	9
11	6	26	10
12	6	27	10
13	7	28	10
14	7	29	10
15	7	30	10

크게 jump_Count가 빨간색과 파란색으로 칠해봈다. 역시나 두루뭉실하게나 보일 뿐 이런 규칙이다! 라는 확답은 내릴 순 없었다. 그러던 중, 루트를 씌우면 어떨까 라는 생각이 들었다.

x2y_Distance 값이 1과 2일 때를 제외하고 x2y_Distance 값에 루트를 씌우면 2 * 2 = 4, 3 * 3 = 9, 4 * 4 = 16, ... 값을 확인할 수 있다. 규칙이 조금이지만 뭔가 명료하게 보이는 것 같다.

x2y_Distance	jump_Count	x2y_Distance	jump_Count
1	1	16	7
2	2	17	8
3	3	18	8
4	3	19	8
5	4	20	8
6	4	21	9
7	5	22	9
8	5	23	9
9	5	24	9
10	6	25	9
11	6	26	10
12	6	27	10
13	7	28	10
14	7	29	10
15	7	30	10

x2y_Distance에 루트를 씌웠을 때 정수가 나오는 값에 빨간 색 글자로 표기해봤다. 신기하게도 그 값은 우리가 바로 직전에 빨간 색과 파란 색으로 표기했던 그 표에서 빨간 색으로 칠한 칸 수 / 2, 파란 색으로 칠한 칸 수 / 2였다.

예를 들어, x2y_Distance이 9라고 가정해보자. 9는 3 * 3, 3의 제곱이다. 그리고 위 표에서 x2y_Distance == 9에 해당하는 jump_Count의 값은 5. 5가 세 번 반복되고, 6 또한 세 번 반복된다. 세 번 반복되는 수는 총 여섯 개. 9 - 5는 6 / 2, 3. 3번째에 위치하고 있다. 다른 경우도 모두 위 조건을 만족한다. x2y_Distance 값이 4일 때 2번째에 위치하고 있고, 9일 때는 3, 16일 때는 4, 25일 때는 5번째에 위치하여 모두 같은 조건을 만족하고 있다.

패턴의 첫 번째 단추를 끼웠다. 이를 바탕으로 마저 다른 단추를 끼워나가기만 하면 된다.


      
      
      
    
    
      <c++ />
    
// x_Value = 3
// y_Value = 10
// x2y_Distance = 7
// sqrt(x2y_Distance) = 2.645751311064591

// sqrt_Value = floor(sqrt(x2y_Distance)) = 2
// pow_Value = pow(sqrt_Value, 2.0) = 4

sqrt_Value = floor(sqrt(x2y_Distance));
pow_Value = pow(sqrt_Value, 2.0);

if (pow_Value >= x2y_Distance){
	jump_Count = sqrt_Value * 2 - 1;
}
else if (pow_Value < x2y_Distance && x2y_Distance <= (sqrt_Value + pow_Value)){
	jump_Count = sqrt_Value * 2;
}

// else if ( 7 > 6 ){
// jump_Count = 5;
// }
else if (x2y_Distance > (sqrt_Value + pow_Value)){
	jump_Count = sqrt_Value * 2 + 1;
}

x2y_Distance 값에 루트를 씌우고 소수점을 뗀 후에, 제곱을 하면 바로 우리가 빨간 색으로 칠한 x2y_Distance 값이 나온다.

x_Value 값이 3, y_Value 값이 10이라고 가정하자. x2y_Distance 값은 7로, 여기에 루트를 씌우면 2.645751311064591라는 값이 나오는데 소수점을 떼고 제곱을 하면 4. 우리가 빨간 색으로 칠한 x2y_Distance : 4가 나온다. x2y_Distance가 4일 때, jump_Count 값은 3이다.

이를 바탕으로 마저 단추를 다 채우고 정리하면 아래와 같이 x2y_Distance 값의 범위에 따른 식으로 정리할 수 있다.

1. pow_Value >= x2y_Distance
-> jump_Count = sqrt_Value * 2 - 1

2. sqrt_Value + pow_Value >= x2y_Distance > pow_Value
-> jump_Count = sqrt_Value * 2

3. x2y_Distance > sqrt_Value + pow_Value
-> jump_Count = sqrt_Value * 2 + 1

자, 이렇게 하고 돌려보면 에러가 나온다. 바로 x2y_Distance 값이 1, 2, 3일 때인데 switch ~ case ... 함수를 사용해 따로 정리해줬다.


      
      
      
    
    
      <c++ />
    
if (x2y_Distance <= 3){
	switch (x2y_Distance){
    case 1:
    jump_Count = 1;
    break;
    
    case 2:
    jump_Count = 2;
    break;
    
    case 3:
    jump_Count = 3;
    break;
    }
}

정리하자면 아래와 같다.


      
      
      
    
    
      <c++ />
    
#include <stdio.h>
#include <math.h>

// 공간이동 장치 실행 함수
int activate_Machine(int, int);

int main(){
	// x좌표와 y좌표를 받아올 int형 변수 x_Val, y_Val;
    int i, x_Val, y_Val;
    int testCase = 0;

    scanf("%d", &testCase);
    
    for (i = 0 ; i < testCase ; i++){
        x_Val = y_Val = 0;
        scanf("%d %d", &x_Val, &y_Val);
        
        // x좌표와 y좌표를 받아 activate_Machine 함수에 매개변수로 전달
        printf("%d\n", activate_Machine(x_Val, y_Val));
    }
}

// activate_Machine 함수
int activate_Machine(x_Val, y_Val){

    // x2y_Distance : x 좌표와 y 좌표 사이의 거리
    // jump_Count : 워프를 카운트하기 위한 변수
    // sqrt_Value : 제곱한 값을 담아두기 위한 변수
    // pow_Value : 루트를 씌운 값을 담아두기 위한 변수
    int x2y_Distance, jump_Count, sqrt_Value, pow_Value;
    
    jump_Count = sqrt_Value = pow_Value = 0;
    x2y_Distance = y_Val - x_Val;

    if (x2y_Distance <= 3){
        switch (x2y_Distance)
        {
        case 1:
            jump_Count = 1;
            break;
        case 2:
            jump_Count = 2;
            break;
        case 3:
            jump_Count = 3;
            break;
        }
    }
    else{
        sqrt_Value = floor(sqrt(x2y_Distance));
        pow_Value = pow(sqrt_Value, 2.0);

        if (pow_Value >= x2y_Distance){
            jump_Count = sqrt_Value * 2 - 1;
        }
        else if (pow_Value < x2y_Distance && x2y_Distance <= (sqrt_Value + pow_Value)){
            jump_Count = sqrt_Value * 2;
        }
        else if (x2y_Distance > (sqrt_Value + pow_Value)){
            jump_Count = sqrt_Value * 2 + 1;
        }
    }

    return jump_Count;
}

저작자표시 (새창열림)

'프로그래밍 > 백준 알고리즘' 카테고리의 다른 글

[C] 오븐 시계 (백준 알고리즘 2525번) (0)	2022.03.05
[C] 당근 밭 (백준 알고리즘 23239번) (0)	2022.03.04
[C] 1998년생인 내가 태국에서는 2541년생?! (0)	2022.02.13
[C] ??! (0)	2022.02.11
[C] 설탕 배달 (백준 알고리즘 2839번) (0)	2021.10.02

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

0.0.1.

1. 1. 문제

1.1. 💡 문제

1.2. 💡입력

1.3. 💡 출력

2. 2. 풀이

3. 3. 메모

'프로그래밍 > 백준 알고리즘' 카테고리의 다른 글

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역

0.0.1.

1. 1. 문제

1.1. 💡 문제

1.2. 💡입력

1.3. 💡 출력

2. 2. 풀이

3. 3. 메모

'프로그래밍 > 백준 알고리즘' 카테고리의 다른 글

검색 태그

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역