[백준 2024/01/16] 1011번

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

1011번: Fly me to the Alpha Centauri

 

1. 접근 방법

굉장히... 허무하면서도...힘들었던... 그런 문제이다. ㅠㅠㅠ....

 

처음에 접근 하였던 방법은, 

끝에서 부터 하나씩 전체 거리에서 빼가면서 진행하고자 하였다.

만약, 빼고자 하는 값이 전체 거리를 음수로 만든다면, 1을 추가해주거나, 그 거리에 맞는 값을 추가해주는.. 그런..

12321...이거나..

12211...

121

11

(말로 설명을 너무 못한다 나..)

 

그래서 다음과 같이 식을 구성하였다. 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String num = scanner.nextLine();
        int repeat = Integer.parseInt(num);

        for(int i = 0; i<repeat;i++){
            String line = scanner.nextLine();
            String[] xy = line.split("\\s+");
            int distance = Integer.parseInt(xy[1]) - Integer.parseInt(xy[0]);

            int move = 0;
            int n = 1;

            do{
                if (distance<2*n) {
                    if(distance==n){
                        move +=1;
                        //Systehttp://m.out.print("1:");
                        System.out.println(move);
                        break;
                    }
                    else{
                        int q = distance/n;
                        distance-=q*n;
                        move+=q;
                        move+=distance;
                        //Systehttp://m.out.print("2:");
                        System.out.println(move);
                        break;
                    }
                }
                else{
                    distance = distance - 2*n;
                    move +=2;
                    //Systehttp://m.out.print("3:");
                    //System.out.println(move);
                }
                n+=1;
            }while(true);
        }

    }
}

총 거리가 9 까지는, 어느정도 맞게 진행되었다.

그 이후부터는.. ㅠ 틀린 답을 내놓기 시작했다.

.. 아마 위 코드가 모든 경우의 수를 다 수용할 수 없었나보다.

 

그래서 naver에 여러 코드들을 찾아보기 시작했다. 

 

규칙을 이용하여 코드를 구성하는 것이었다.

아주......허무........했다.......ㅠ

rough draft

이런식으로 구성하였고, n은 초록색 선의 값을 의미한다.

n(n+1)을 이용하여, 총거리에 해당하는 n을 구할 수 있다. 

while 문을 이용해서, n의 값을 구하였다.

distance<= n*(n+1) 

하지만 이런식으로 n을 구할 경우 시간 초과가 되어서 다른 접근을 필요로 했다. 

 

우선 시간 초과가 된 코드는 다음과 같다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String num = scanner.nextLine();
        int repeat = Integer.parseInt(num);

        for(int i = 0; i<repeat;i++){
            String line = scanner.nextLine();
            String[] xy = line.split("\\s+");
            int distance = Integer.parseInt(xy[1]) - Integer.parseInt(xy[0]);

            int n = 0;

            while(true){
                if(distance<= n*(n+1)){
                    break;
                }
                n+=1;
            }
            if(Math.pow(n,2)>= distance){
                System.out.println(2*n-1);
            }
            else{
                System.out.println(2*n);
            }
        }

    }
}

새롭게 접근 한 방법은 루트를 이용하는 것이었다.

 

루트를 하고 버림을 통해, max라는 변수에 저장해 주었다.

 

max* max를 기준으로 + max or -max에 따라 루트-> 버림 된 값이 달랐다.

하지만 넘겨줘야하는 n의 값은 동일했어야 했기에, 

거리가 + max or - max에 따라 +1을 해줄지 말지 결정하였다.

 

이후 n의 값을 넘겨주어, n의 제곱이 distance의 위 아래인지 결정하여 배분해주었다.

(말로 설명하기 너무 어렵다..ㅠ)

 

2. 코드

import java.util.Scanner;

public class b1011 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String num = scanner.nextLine();
        int repeat = Integer.parseInt(num);

        for(int i = 0; i<repeat;i++){
            String line = scanner.nextLine();
            String[] xy = line.split("\\s+");
            int distance = Integer.parseInt(xy[1]) - Integer.parseInt(xy[0]);

            int n = 0;

            int max = (int)Math.sqrt(distance);

            if(max == Math.sqrt(distance)){
                n = max;
            }
            else if(distance <= max*max + max){
                n = max;
            }
            else{
                n = max + 1;
            }

            if(Math.pow(n,2)>= distance){
                //System.out.print("2:");
                //System.out.println(Math.pow(n,2));
                System.out.println(2*n-1);
            }
            else{
                System.out.println(2*n);
            }

            //System.out.println(distance);

        }

    }
}