티스토리 뷰

PS/boj

boj)1459 - 걷기

kingsubin 2020. 8. 31. 19:34
import java.io.*;
import java.util.StringTokenizer;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        long X = Long.parseLong(st.nextToken()); // ~10억
        long Y = Long.parseLong(st.nextToken()); // ~10억
        long W = Long.parseLong(st.nextToken()); // 수평 ~10,000
        long S = Long.parseLong(st.nextToken()); // 대각선 ~10,000

        /**
         * 이동 방법의 경우의 수
         * 1. 수평으로만 이동하는 경우
         * 2. 대각선으로만 이동하는 경우
         * 3. 대각선 + 수평의 경우
         */
        long cost1, cost2, cost3;

        // 1. 수평으로만 이동하는 경우
        cost1 = (X+Y) * W;

        // 2. 대각선으로만 이동하는 경우
        // 2-1. 홀수일 경우 대각선 이동 후 수평이동 1칸
        // 2-2. 짝수일 경우 대각선으로만 이동 가능
        if ((X + Y) % 2 == 0) cost2 = Math.max(X, Y) * S;
        else cost2 = ((Math.max(X, Y) - 1) * S) + W;

        // 3. 대각선 + 수평 : 대각선으로 최대한 이동 후 수평 이동
        cost3 = (Math.min(X, Y) * S) + (Math.abs(X-Y) * W);

        long ans = Math.min(Math.min(cost1, cost2), cost3);
        System.out.println(ans);
    }
}

 

- 되는것 같은데 안되고 이러다가 결국 다른 풀이 봄

- 다른 풀이 보고 수정후에 다시 제출 했는데도 계속 틀림

- 알고보니까 int가 아니라 long을 썻어야함 .... 계속 int, long 잘못 씀 

 

- 처음에는 이렇게 안 풀고 홀짝으로 생각했는데 그거는 경우의수가 너무 여러개로 갈렸음

- 이렇게 비용의 가짓수로 나누는게 제일 좋은듯

 

1. 이동하는데 걸리는 최솟값 구하기

2. 목적지까지 이동하는 비용의 경우의 수를 3가지로 분류한다.

3. 1) 수평으로만, 2)대각선으로만 ,3)대각선+수평

4. 각각에서의 비용 구하기는 어렵지 않으니 전부의 비용을 구한 뒤 최솟값을 구한다.

 

 

 


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

'PS > boj' 카테고리의 다른 글

boj)1260 - DFS와 BFS  (0) 2020.09.03
boj)18352 - 특정 거리의 도시 찾기  (0) 2020.09.02
boj)12018 - Yonsei TOTO  (0) 2020.08.31
boj)2012 - 등수 매기기  (0) 2020.08.31
boj)1911 - 흙길 보수하기  (0) 2020.08.31