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