백준 2159 케익 배달 python, java

DP를 이용해 목적지의 중앙, 상, 하, 좌, 우에 가장 짧은 거리를 기록하며 풀이했다.
그런데 그것보다 이번 문제를 통해 자바 타입관련해서 간단하지만 배운게 있다.

📜 문제 바로 가기 : 케익 배달

제출코드

파이썬

import sys
input = sys.stdin.readline

def isRange(i, j):
    if 0 <= i < 100000 and 0 <= j < 100000:
        return True
    return False

N = int(input())

DP = [[0,0,0,0,0] for _ in range(N+1)]

pos = [tuple(map(int, input().split())) for _ in range(N+1)]
delta = [(0,0), (-1,0), (1,0), (0,-1), (0,1)] # 중앙, 상, 하, 좌, 우

si, sj = pos[0][0], pos[0][1]
for i in range(5):
    DP[1][i] = abs(si - (pos[1][0] + delta[i][0])) + abs(sj - (pos[1][1] + delta[i][1]))

for k in range(2, N+1):
    for a in range(5):
        i, j = pos[k][0] + delta[a][0], pos[k][1] + delta[a][1] # 도착좌표
        dis = 200000 * k
        if isRange(i, j):
            for b in range(5):
                pi, pj = pos[k-1][0] + delta[b][0], pos[k-1][1] + delta[b][1] # 출발좌표
                dis = min(dis, abs(i-pi) + abs(j-pj) + DP[k-1][b])

        DP[k][a] = dis

print(min(DP[N]))

자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
        int N = Integer.parseInt(st.nextToken());
        int[][] pos = new int[N+1][2];
        for (int i = 0; i < N+1; i ++) {
            st = new StringTokenizer(br.readLine());
            pos[i][0] = Integer.parseInt(st.nextToken());
            pos[i][1] = Integer.parseInt(st.nextToken());
        }

        int[][] delta = new int[][]{{0,0}, {-1,0}, {1,0}, {0,-1}, {0,1}};
        long[][] DP = new long[N+1][5];
        int si = pos[0][0];
        int sj = pos[0][1];
        for (int i = 0; i < 5; i ++) {
            DP[1][i] = abs(si-(pos[1][0]+delta[i][0])) + abs(sj-(pos[1][1]+delta[i][1]));
        }

        for (int k = 2; k < N+1; k++) {
            for (int a = 0; a < 5; a++) {
                int i = pos[k][0] + delta[a][0];
                int j = pos[k][1] + delta[a][1];
                // long dis = Long.MAX_VALUE;
                long dis = 200000L * k;
                if (isRange(i, j) == true) {
                    for (int b = 0; b < 5; b++) {
                        int prei = pos[k-1][0] + delta[b][0];
                        int prej = pos[k-1][1] + delta[b][1];
                        dis = Math.min(dis, abs(i-prei) + abs(j-prej) + DP[k-1][b]);
                    }
                }
                DP[k][a] = dis;
            }
        }
        long ans = DP[N][0];
        for (int i = 1; i < 5; i++) {
            ans = Math.min(ans, DP[N][i]);
        }
        System.out.println(ans);
    }
    public static int abs(int i) {
        if (i < 0) {
            return -i;
        }
        return i;
    }
    public static boolean isRange(int i , int j) {
        if ( 0 <= i && i < 100000 && 0 <= j && j < 100000 ) {
            return true;
        }
        return false;
    }
}

---

접근방법

k번째 케익 배달이 가능한 좌표 중앙, 상, 하, 좌, 우에서 가장 짧은 길을 기록해 간다.

자바 long 타입

long c = a * b 에서 a, b 둘다 int타입일 때 주의해야한다. a * b 계산값이 int 범위를 넘어가게 되면 엉뚱한 값이 나와버린다.

Integer a = Integer.MAX_VALUE;
Integer b = 2;
        
Long c = (long) (a * b); 
Long d = (long) a * b; 

System.out.println(c); // -2         엉뚱한 값
System.out.println(d); // 4294967294 기대한 값

따라서 범위를 잘 생각해보고 long 변환이 필요하다면 둘 중 한 값이라도 long 변환을 하여 연산을 해주자.

그리고 아주 큰 값으로 초기화가 필요한 부분이 있다면 그냥 Long.MAX_VALUE 이런거 이용하자!

정말 이 부분을 간과해서 몇번을 고민했는지 모른다.
덕분이 이부분은 못 잊을거 같다!