백준 알고리즘 1011번 문제풀이(JAVA)

ㅋㅋ.. 이 문제 어려웠다..!! 이틀 내내 까진 아니지만 고민해서 풀었는데 에러나서 분명 어딘가 문제인데 그걸 어떻게 해결해야할지 몰라서 이 문제는 다른 풀이를 봐버렸다...

 

다른 풀이를 보니까 현타*2222222222222배 와버림. 확실히 난 아직 많이 부족하다. 알고리즘 문제 푸는 감이 부족하다 해야하나. 아니면 그냥 못 푸는 걸까.

 

처음에 방향을 아예 잘못 잡았다. 아, 아예 잘못된 방향인 걸 알았을 때 다 지우고 새로운 방법으로 풀면 되는데 혹시나 내가 푼 방법이 맞지 않을까라는 생각에 검색해보았다...^^ (한심ㅎ) 앞으론 아예 잘못된 거 같을 땐 처음부터 다시 풀자..^^

 

문제 조건에 처음 출발과 도착 직전엔 무조건 1만 이동한다고 나와있다. 이 조건을 잘못 사용한 거 같다. 어차피 1로 동일하니까 아예 구해야하는 거리에서 -2를 해버리고 남은 거리를 계산하려고 했다.

문제에 2번 째 조건으로 직전 이동한 거리-1, +0, +1 거리 중에서만 선택해서 이동할 수 있다는 조건이 있다. 이 조건에서도 선택한 직전 거리랑 앞으로 선택할 거리도 따져줘야 하고 해서 조건 판별해 구해야겠다 라고 생각했다. 최단 횟수를 구하는 문제이니 가장 큰 거리부터 선택해 구하면 되겠다라고 생각해 스택을 이용해 풀었는데 예제 테스트 케이스는 통과했지만 채점에서 에러가 나서 해결못했다. 로직에 분명한 오류가 있다. 근데 그 오류를 일일이 하나하나 다 따져서 해주기엔 코드가 너무 복잡해질 거 같다는 생각을 했다.

 

다음은 내가 작성한 코드이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static int restDistance;
    public static int count = 2;
    public static Stack<Integer> stack;
    public static int selectedNum = 0;

    public static void main(String[] args) throws IOException {

        stack = new Stack<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0;i<T;i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            restDistance = (y-x) - 2;

            stack.push(0);
            stack.push(1);
            stack.push(2);

            while(true) {

                if(restDistance == 0){
                    break;
                }
                int n = stack.pop();
                if(isRight(n)) {
                    if(restDistance == 0){
                        break;
                    }
                    stack.push(selectedNum-1);
                    stack.push(selectedNum);
                    stack.push(selectedNum + 1);
                }

            }


            System.out.println(count);
            stack.clear();
            count = 2;
        }




    }

    public static boolean isRight(int n) {

        if(n > restDistance){
            return false;
        }else {
            selectedNum = n;
            count += restDistance / n;
            restDistance -= n * (restDistance / n);
            return true;
        }

    }

}

 

굉장히 부끄럽다. 하지만 점차 이런 실수를 줄여나가기 위해 코드를 올려본다. 나처럼 생각한 사람 없을까..?

확실히 문제를 제대로 분석안하고 코드를 짜니까 이렇게 구구절절한 코드가 나왔다. 결국 해결도 못하고!!!!

 

그래서 결국 다른 풀이를 봐버렸다. 찾아보니까 대부분 규칙성을 찾아서 금방 쉽게 해결했다. 현타가 또 왔다..^^

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static int restDistance;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0;i<T;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            int distance = y-x;
            int count = 0;

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

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

            System.out.println(count);
        }


    }



}

 

코드는 굉장히 간단하지만 규칙성을 이해하는데 좀 걸렸다. 생각해보니 문제 조건이 다 문제 해결의 핵심 키워드였다. (예전에 맨날 수학 풀 때 선생님이 문제에 답이있다!!!라고 맨날 말씀하셨었는데 선생님 저는 아직도 그걸 못하고 있네요..^^ 나이를 먹어도 왜 변하질 않죠?ㅎ)

 

1. 출발 시, 도착 시 이동거리는 1

2. 직전 이동 거리의 -1,+0,+1 거리 중 하나 선택하여 이동

 

-> 이 두 조건때문에 주어진 거리(distance)에 따라 이동한 거리에 규칙성이 생기고 이동 거리 최댓값과 count의 연관성만 알아내면 문제해결할 수 있다. (distance = 1 일때부터 손으로 직접 적어가며 나열해보면 규칙성을 발견할 것이다.)

 

나중에 또 풀어봐야겠다..