1459번 걷기

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

푸는데 오래 걸렸다.

가로와 세로의 길이의 합이 짝수일 때는 

가로와 세로만 가는 경우 vs 대각선으로만 가는 경우

홀수일 때는

가로와 세로만 가는 경우 vs (큰 변 길이 - 1)번 대각선 이동 + 1번 축 이동

이런 식의 비교인줄 알았다.

하지만 반례가 있었다.

1 4 2 3
correct : 9
wrong : 11
 
1 11 6 7
correct : 67
wrong : 72

하여튼 고려해야할 것은

가로와 세로만 가는 경우 vs 대각선으로 쭉 먼저 이동한 후 + 축으로 쭉 이동하기

이다.

여기에 추가적으로

가로와 세로의 길이의 합이 짝수일 때는 대각선으로만 이동하는 경우까지 비교하고

홀수일 때는 (큰 변 길이 - 1)번 대각선 이동 + 1번 축 이동하는 경우까지 비교한다.

즉, 3개의 비교이다.

import java.io.*;
import java.util.*;
 
public class Main {
    
    static long r, c, w, s;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        r = Long.parseLong(st.nextToken()); // x
        c = Long.parseLong(st.nextToken()); // y
        w = Long.parseLong(st.nextToken());
        s = Long.parseLong(st.nextToken());
        
        if(r > c) {
            // r < c로 만들기
            long t = r;
            r = c;
            c = t;
        }
 
        long rc_move = (r + c) * w;
        long max_diag = r * s + (c - r) * w;
        long ans = Math.min(rc_move, max_diag);
        
        if((r + c) % 2 == 0) {
            ans = Math.min(ans, c * s);
        }
        else {
            ans = Math.min(ans, (c-1)*s + w);
        }
        
        bw.write(String.valueOf(ans) + "\n");
        bw.flush();
        bw.close();
    }
}