[SWEA] 8382. 방향 전환 (Java)

규칙을 찾는다면 매우 간단한 문제!

SW Expert Academy

풀이

탐색 알고리즘을 사용하여 풀 수도 있지만 규칙을 찾는다면 정말 간단하게 풀리는 문제이다.

횟수를 종이에 직접 써보면 아래와 같은 표가 생긴다.

 

 

가로축, 세로축은 n에따라 짝수는 4n, 홀수는 4n+1의 값을 가진다.

보면 1씩 번갈아가면서 값이 바뀌는 것을 확인할 수 있는데 이를 토대로 규칙을 설정하면 된다.

Logic

• (x1, y1)과 (x2, y2)사이의 거리를 절댓값을 취하여 구해놓는다. (dx, dy)
• (n, n) 기준으로 대칭이므로 x를 기준으로 보도록 한다. dx<dy라면 swap해서 dx가 항상 크도록 한다.
• 정답인 ans값을 미리 초기화하는데 ans = (dx / 2) * 4 + (dx % 2)이다.

코드

import java.util.*;
import java.io.*;

public class Solution {
    static int T, x1, y1, x2, y2, ans;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());

        for (int index = 1; index <= T; index++) {
            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());
            ans = 0;

            int dx = Math.abs(x2 - x1);
            int dy = Math.abs(y2 - y1);

            if (dy > dx) {
                int temp = dx;
                dx = dy;
                dy = temp;
            }

            ans = (dx / 2) * 4 + (dx % 2);

            if (dy % 2 == 1) {
                if (dx % 2 == 1) ans++;
                else ans--;
            }

            bw.write("#" + index + " " + ans + "\n");
        }
        br.close();
        bw.close();
    }
}

 

실행결과