[ Baekjoon - 11/11 ] - 1069번: 집으로

• 문제 링크 : https://www.acmicpc.net/problem/1069

1069번: 집으로

 

• 소요 시간 : 3시간..

집으로 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

3987

1032

792

27.123%

문제

은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다.

첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법은 점프하는 것이다. 점프를 하게 되면, T초에 D만큼 움직인다. 점프는 일직선으로만 할 수 있고, 정확하게 D칸만 움직일 수 있다.

위의 두 가지 방법을 이용해서 집에 돌아오는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오. 꼭 한 가지 방법만 사용해야 되는것이 아니고, 두 가지 방법을 적절히 조합해서 가장 빠른 시간을 구하는 것이다.

입력

첫째 줄에 네 정수 X, Y, D, T가 주어진다.

출력

첫째 줄에 집에 돌아오는데 걸리는 시간의 최솟값을 출력한다. 절대/상대 오차는 10-9까지 허용한다.

제한

• 1 ≤ X, Y ≤ 1,000
• 1 ≤ D, T ≤ 10,000

예제 입력 1 복사

6 8 5 3

예제 출력 1 복사

6.0

예제 입력 2 복사

3 4 6 3

예제 출력 2 복사

4.0

예제 입력 3 복사

318 445 1200 800

예제 출력 3 복사

546.9451526432975

예제 입력 4 복사

400 300 150 10

예제 출력 4 복사

40.0

예제 입력 5 복사

6 8 3 2

예제 출력 5 복사

7.0

예제 입력 6 복사

10 10 1000 5

예제 출력 6 복사

10.0

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 128MB
   • 문제
     
     • 1 ≤ X, Y ≤ 1,000, 1 ≤ D, T ≤ 10,000
     • (X,Y)에서 (0,0)으로 빠르게 가는 것이 목표
     • 가는 방법은 2가지로,
       첫번째는 걸어서 1초에 1만큼 가는 것이고,
       두번째는 뛰어가는데, T초에 D만큼 가는 것
     • (0,0)에 도착할 수 있는 최단시간을 출력하는 문제
   • 이해
     • 너무나도 당연하게.. 지도의 좌표라고 생각해서 1초에 1이 상하좌우만 가능한 것인지, 대각선도 1이라 하는건지 같은 생각을 했다..
     • 이 문제에서 (X,Y)는 지도의 칸이 아닌 좌표평면의 좌표였어서 기하학적 분석을 했어야했는데.... 역시 고정관념은 무서운것같음..ㅠ
2. 문제를 익숙한 용어로 재정의와 추상화
   • 문제를 이해하기 위해 재정의와 추상화를 한 흔적은 없고, 입력 1 의 출력값이 왜 6이 나오는지 오래 고민했다.
   • 사실 계속 고민해도 모르겠어서 질문하기를 보았는데 아무도 나같은 생각을 한 사람이 없었다.. 그래서 내가 어딘가를 굉장히 잘못 해석했구나 하며 문제를 여러번 읽으며 시도하다가, 맵이 아닌 좌표평면상에서의 거리임을 깨달았다 ㅠ
3. 문제를 어떻게 해결할 것인가
   • 접근 - 기하학적 분석..)
     • 맵 상의 구성이 아닌 좌표평면에서의 케이스들이므로, 조건만 잘 잡아내면 풀릴 문제라고 생각되었다.
     • 처음에는 (0,0)과 (X,Y)를 중심으로 하는 원들의 관계를 파악하여 줄여나가는 방식으로 풀어야한다고 생각되었지만 너무많은 분기가 나타나서 아 이건 아닐거야 부정했음..;;(??)
     • 그렇게 고민하다가, 우선 어떤 접근을 하더라도 두 점사이의 거리로 판단하긴 해야할것이라 생각했기 때문에
       해당 거리가 점프가 가능한 거리인지 아닌지로 분기를 나누고자 했다.
     • 문제 풀면서 정리한게 내가 아니면 알아보기 어려울것 같아서 다시 그려보았다.

     • 

     • 점프가 불가능하다면,
       최단거리 내에서는 걷기만 가능할 것이다.
       그런데, 최단거리 내에서만 점프가 불가능할 뿐이지, 최단거리가 아닌 다른 곳으로 점프했다가 걸어서 도착과 다른 곳으로 점프했다가 다시 점프해서 도착은 가능한 형태이므로 이중 효율적인 방법으로 선택하면 된다.
     • 점프가 가능했다면,
       우선 걷기만으로 도착하는 것은 당연히 가능하다.
       그리고 가능한 만큼 점프를 뛰고 모자란 거리가 있으면 걸어서 도착과 가능한 만큼 점프를 뛰고 한번 더 뛰어서 도착 하는 경우가 있으므로 이중 효율적인 방법으로 선택하면 된다.
4. 위 계획을 검증
   • 기하학적인 요소가 많아서.. 수학적으로 증명해야하는데, 거기까진 무리ㅠ
   • 그래도 풀어놓은 분기를 따라가면 납득할 수 있을거라 생각한다 ㅎㅎ ㅠ
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main {
            static int X,Y,D,T,possiJump;
            static double dist, ans;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
                StringTokenizer st = new StringTokenizer(br.readLine());
                X = Integer.parseInt(st.nextToken());
                Y = Integer.parseInt(st.nextToken());
                D = Integer.parseInt(st.nextToken());
                T = Integer.parseInt(st.nextToken());
        
                // 최단거리
                dist = Math.sqrt(X*X + Y*Y);
                // 최단거리 안에서의 최대가능 점프 수
                possiJump = (int) dist/D;
        
                // 최단거리 안에서 점프가 가능했다면
                if(possiJump > 0)
                    // (걷기만) vs (뛸 수 있는만큼 뛰고 나머지는 걷기) vs (뛸수있는 횟수만큼 뛰고 한번 더 뛰어서 돌아오기) 중 최솟값이 정답
                    ans = Math.min(Math.min(dist, dist - possiJump*(D-T)), (possiJump+1)*T*1.0);
                // 최단거리 안에서 점프가 불가능하다면
                else{
                    // (걷기만) vs (한번 점프하고 역방향으로 걷기) vs (한번 점프해서 더 나아가고 역방향 점프) 중 최솟값이 정답
                    ans = Math.min(Math.min(dist, (possiJump+1)*D-dist + T), T*2.0);
                }
                bw.write(ans+"\n");
                bw.flush();
            }
        }

   2. Python 3

      • import sys
        import math
        # sys.stdin = open("input.txt")
        input = sys.stdin.readline
        
        def solution():
            # 최단거리
            dist = math.sqrt(X * X + Y * Y)
            # 최단거리 안에서의 최대가능 점프 수
            possiJump = dist // D
        
            # 최단거리 안에서 점프가 가능했다면
            if possiJump > 0:
                # (걷기만) vs (뛸 수 있는만큼 뛰고 나머지는 걷기) vs (뛸수있는 횟수만큼 뛰고 한번 더 뛰어서 돌아오기) 중 최솟값이 정답
                ans = min(dist, dist - possiJump * (D - T), (possiJump + 1) * T * 1.0)
                # 최단거리 안에서 점프가 불가능하다면
            else:
                # (걷기만) vs (한번 점프하고 역방향으로 걷기) vs (한번 점프해서 더 나아가고 역방향 점프) 중 최솟값이 정답
                ans = min(dist, (possiJump+1) * D-dist + T, T * 2.0)
            return ans
        
        if __name__ == '__main__':
            X,Y,D,T = map(int, input().split())
            print(solution())

 

• 결과