[파이썬, 자바] BOJ_1459(걷기)

문제

 

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

1459번: 걷기

---

 

해설

 

첫번째 풀이

   

평행 시간(w) * 2와  대각선 시간(s)을 비교를 해서 풀었다.

 -> (0, 0)에서 (1, 1)까지 처럼 똑같은 곳까지 가는데 걸리는 시간을 판단하기 위해 평행 이동을 했을 때와 대각선 이동을  했을 때를 비교하기 위해서이다.

 

1) 2 * w < s (평행이 더 빠를 때)

2) 2 * w >= s (대각선이 더 빠를 때)

  2 - 1) x + y가 짝수일 때

  2 - 2) x + y가 홀수일 때

 

위 처럼 생각해서 풀었는데, 생각하지 못했던 조건이 하나 더 있었다.

대각선 이동과 평행 이동을 같이 할 때 최단시간이 나오는 경우가 있었다.

---

두번째 풀이

 

위의 실패 경험을 발판 삼아 세가지 경우를 나눠 비교했다.

 

1) 평행 이동만 하는 경우

2) 짝수, 홀수에 따라 다른 이동을 하는 경우

3) 대각선 + 평행 이동을 하는 경우

 

1. 평행 이동만 하는 경우

 

 - x와 y 값을 더해 이동해야 하는 횟수를 구한 다음 w(평행 이동)를 곱해주면 된다

2. 짝수, 홀수에 따라 다른 이동을 하는 경우

 

 - x + y가 짝수라면 : x, y 중에 큰 값을 골라 s(대각선 이동) 값만 곱해주면 된다

  -> 대각선 개수가 딱 맞아 떨어지기 때문

짝수

 

 - x + y가 홀수라면 : x, y 중 큰 값에서 1을 빼주고 s(대각선 이동) 값을 곱해준 후, 빼준 1만큼 w(평행 이동)을 더해주면 된다

  -> 대각선 개수가 딱 맞아 떨어지지 않기 때문

홀수

 

3. 대각선 + 평행 이동을 하는 경우

 

 - 이 경우를 생각해야 하는 이유는, 이렇게 했을 때가 최단 시간인 경우가 있어서이다.

 - x : 1, y : 4, w : 2, s : 3인 경우가 이와 같은 경우에 해당한다.

  -> 내 첫 번째 풀이를 생각해보면, 2 * w가 s보다 크기 때문에 홀수인 경우만 생각하면 최단 시간이 나올 것 같은데

그렇게 풀이를 하면 답이 11이 나온다.

  -> 그러나 3번 처럼 푼다면 답이 9가 나온다. 아래의 그림들을 보자.

 

 

왼) 평행 이동을 한 경우 / 오) 홀수 이동을 한 경우

대각선 + 평행 이동을 한 경우

 - 위의 3가지 그림을 보면 마지막 풀이가 최단 거리인 것을 한 눈에 알 수 있다.

  -> 대각선 + 평행 이동은 x, y 값 중 작은 값 만큼만 대각선 이동을 하고 나머지에 대해선 평행 이동을 하는 것이다.

---

코드

 

-파이썬

#백준 1459(걷기)

x, y, w, s = map(int, input().split())  #집의 위치(x, y), 평행, 대각선

#평행 이동
move1 = (x + y) * w

#짝수, 홀수에 따른 이동
if (x + y) % 2 == 0:  #x + y가 짝수라면
    move2 = max(x, y) * s
else:  #홀수라면
    move2 = (max(x, y) - 1) * s + w
    
#대각선 + 평행 이동
move3 = (min(x, y) * s) + ((max(x, y) - min(x, y)) * w)

res = min(min(move1, move2), move3)

print(res)

 

- 자바

//백준 1459(걷기)
import java.util.*;
import java.io.*;

public class Boj_1459 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		long x = Integer.parseInt(st.nextToken());  //집 위치 x좌표
		long y = Integer.parseInt(st.nextToken());  //집 위치 y좌표
		long w = Integer.parseInt(st.nextToken());  //평행 이동
		long s = Integer.parseInt(st.nextToken());  //대각선 이동
		
		//평행 이동
		long move1 = (x + y) * w;
		
		//짝수, 홀수에 따른 이동
		long move2;
		if((x + y) % 2 == 0) {  //x + y가 짝수면
			move2 = Math.max(x, y) * s;
		}
		else {  //x + y가 홀수면
			move2 = (Math.max(x, y) - 1) * s + w;
		}
		
		//대각선 + 평행 이동
		long move3 = (Math.min(x, y) * s) + (Math.abs(x - y) * w);

		
		System.out.println(Math.min(Math.min(move1, move2), move3));
	}

}

자바는 정수형을 잘 체크해줘야 한다.

"X와 Y는 1,000,000,000보다 작거나 같은 음이 아닌 정수이고, W와 S는 10,000보다 작거나 같은 자연수" 라고 명시되어있기 때문에,

int형을 쓰게 된다면 연산을 다 할 수 없으니 long형을써줘야 한다.