boj 1011 Fly me to the Alpha Centauri (c++)

 

 

 

#include <iostream>
#include <cmath>
using namespace std;

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T;
    
    for(int i = 0; i < T; i++) {
        long long x, y;
        cin >> x >> y;
        
        long long distance = y - x;
        
        int j = 1;
        int cnt = 0;
        int idx = 0;
        while(idx == 0){
            if(distance == pow(j, 2)){
                cnt = 2 * j - 1;
                idx = 1;
                distance = 0;
            }
            else if(distance > pow(j, 2) && distance < pow(j + 1, 2)){
                cnt = 2 * j - 1;
                idx = 1;
                distance -= pow(j, 2);
            }
            j++;
        }
        j--;
        while(distance > 0) {
            if(distance >= j) {
                distance -= j;
                cnt += 1;
            }
            else  {
                distance = 0;
                cnt += 1;
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}

제곱함수인 pow를 이용하였다. ( <cmath>를 include 해줘야 함 )

1+2+...+n+(n-1)+...+1 = n^2    <- 이 규칙을 이용하였다.

거리가 12라고 하면 3^2 < 12 < 4^2 이므로 j = 3이 된다.

그러므로 거리가 12인 식은 최대 이동 가능 거리가 3인 것이다.

이렇게 원래 거리에서 확정된 최소 거리 (3^2)를 빼고 나머지는 최대 3 최소 1을 적절히 빼서 카운트를 한다.

 

j++를 해줬다가 바로 j--를 해주는 것은 모양새가 좀 별로긴 한데,

괜히 제어조건을 걸어서 쓸데없이 조건 체크를 하는 것보다 저렇게 하는 게 더 효율적일 것 같아서 그냥 냅뒀다.

 

사담_

내 코드는 실행시간이 4ms가 나왔는데 밑에 0ms가 나온 코드가 있었다.

코드를 보아하니 c와 c++의 차이인 것 같기도 한데 확실히 내 코드보다 간단하게 문제를 해결해서 한 번 리뷰해보려고 한다.

#include <stdio.h>
 
int main() {
    int T;
    unsigned int x, y;
    scanf("%d", &T);
    unsigned int sub;
    unsigned int n1;
    unsigned int n2;
    int j;
 
    for (int i = 0; i < T; i++) {
        scanf("%u %u", &x, &y);
        sub = y - x;
        n1 = 0; n2 = 0; j = 0;
        while (n1 < sub) {
            n2 += j * 2;
            n1 += ++j * 2;
        }
        printf("%d\n", n1 - sub < j ? j * 2 : j * 2 - 1);
    }
    return 0;
}​

sub = 거리

n1 = ?

n2 = ?

와 ?~ 모르겠다~