DP / (Bitonic Tour )

[WonYong-Jang]

현상금 사냥꾼 김정은 / 백준 10272

아이디어

• 두사람을 동시에 출발시켜 N으로 이동 !
• 두사람이 동시에 똑같은 곳에 가면 안됨

  DP[i][j] : A 라는 사람이 i 지점에, B라는 사람이 j 라는 지점에 있을때의 최단 거리

일반적 방법

• for문을 쉽게 구현하기 위해서

  i < j 조건 ==> dp[6][3] 과 dp[3][6] 똑같은 값이기 때문에

  2차원 배열을 절반만 사용!! (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) 순으로 이동!

dp[1][1] = 0; // 똑같은점 있음 안됨 dp[1][2] = dis(1,2); // i < j 처음 이동시켜 놓고 시작 for(int i=1; i < N; i++) { for(int j = i+1; j < N; j++) // 1 ~ N-1 까지 이동 { int k = j + 1; // k : 다음 방문할 곳 / // i에서 이동할 경우 => dp[k][j] = dis(i,k) + dp[i][j] // j에서 이동할 경우 => dp[i][k] = dis(j,k) + dp[i][j] dp[j][k] = min(dp[j][k], dis(i,k) + dp[i][j]); // i < j 로 정의 했으니 바꿔도 동일함! dp[i][k] = min(dp[i][k], dis(j,k) + dp[i][j]); } } double ans = INF; for(int i=1; i < N; i++) // N-1 ~ 에서 N { ans = min(ans, dp[i][N] + dis(i,N)); } System.out.println(ans);

public class baek10272 {

    static final double INF = 2e9;
    static int N;
    static double[][] point = new double[550][2];
    static double[][] dp = new double[550][550]; 
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int testCase = Integer.parseInt(st.nextToken());
        for(int n=1; n <= testCase; n++)
        {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            int dx =0, dy =0;
            for(int i=1; i<= N; i++)
            {
                st = new StringTokenizer(br.readLine());
                dx = Integer.parseInt(st.nextToken());
                dy = Integer.parseInt(st.nextToken());
                point[i][0] = dx; point[i][1] = dy;
                for(int j=1; j<= N; j++)
                {
                    dp[i][j] = INF;
                }
            }

            dp[1][1] = 0; // 똑같은점 있음 안됨 
            dp[1][2] = dis(1,2); // i < j 처음 이동시켜 놓고 시작 
            for(int i=1; i < N; i++)
            {
                for(int j = i+1; j < N; j++) // 1 ~ N-1 까지 이동 
                {
                    int k = j + 1; // k : 다음 방문할 곳 / 
                    // i에서 이동할 경우 => dp[k][j] = dis(i,k) + dp[i][j]
                    // j에서 이동할 경우 => dp[i][k] = dis(j,k) + dp[i][j]
                    dp[j][k] = min(dp[j][k], dis(i,k) + dp[i][j]);
                    dp[i][k] = min(dp[i][k], dis(j,k) + dp[i][j]);
                }
            }
            double ans = INF;
            for(int i=1; i < N; i++) // N-1 ~ 에서 N 
            {
                ans = min(ans, dp[i][N] + dis(i,N));
            }
            System.out.println(ans);
        }
    }
    public static double min(double a, double b) { return a > b ? b : a; }
    public static double dis(int a, int b)
    {
        return Math.sqrt( (point[a][0]-point[b][0])*(point[a][0]-point[b][0]) + (point[a][1]-point[b][1])*(point[a][1]-point[b][1]) );
    }
}

메모이제이션

-

관련 문제

• https://www.acmicpc.net/workbook/view/1809

[WonYong-Jang]

색 상환 문제 ( koip)

D[i] : i개의 칸이 일렬로 놓여있고, K개의 색으로 색칠한다. 이때 인접한 것은 다른 색으로 칠해야 한다. 그리고 1번과 i번의 색도 다른 색으로 칠한다.

• 초기값 D[1] = 0 // D[i] 정의를 1과 i가 다르다고 했으므로 0 D[2] = K*(K-1)

D[i] = (K-1)D[i-2] + D[i-1](K-2)

N >= 2 인 경우 D[i] 가 정답 N = 1 인 경우 K가 정답

백준 색상환 2482