[BOJ 15822 // C++] Ah-Choo!

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 15822번 문제인 Ah-Choo!이다.
문제는 아래 링크를 확인하자.

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

15822번: Ah-Choo!

첫번째 파형의 [0,x] 구간과 두번째 파형의 [0,y] 구간 사이의 최소거리를 dp[x][y]라 하자. 이 값은 첫번째 파형의 시점 x와 두번째 파형의 시점 y 사이의 두 파형의 오차와 나머지 구간의 오차 중 최솟값, 즉 {첫번째 파형의 [0,x-1]구간과 두번째 파형의 [0,y-1] 구간 사이},  {첫번째 파형의 [0,x-1]구간과 두번째 파형의 [0,y-1] 구간 사이}, {첫번째 파형의 [0,x-1]구간과 두번째 파형의 [0,y-1] 구간 사이} 세 값중 가장 작은 값을 합한 것으로 계산할 수 있음을 관찰하자.

 

위의 관계를 이용해 점화식을 세워 메모이제이션을 통한 dp를 진행하는 프로그램을 작성해 문제를 해결하자. x=0 또는 y=0인 케이스에 대한 예외처리에 유의하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N;
ll A[2000], B[2000];
ll dp[2000][2000];
bool visited[2000][2000];

ll func(int i, int j) {
	if (visited[i][j]) return dp[i][j];
	visited[i][j] = 1;
	return dp[i][j] = min(func(i - 1, j - 1), min(func(i, j - 1), func(i - 1, j))) + (A[i] - B[j]) * (A[i] - B[j]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < N; i++) cin >> B[i];

	dp[0][0] = (A[0] - B[0]) * (A[0] - B[0]), visited[0][0] = 1;
	for (int i = 1; i < N; i++) dp[i][0] = dp[i - 1][0] + (A[i] - B[0]) * (A[i] - B[0]), visited[i][0] = 1;
	for (int i = 1; i < N; i++) dp[0][i] = dp[0][i - 1] + (A[0] - B[i]) * (A[0] - B[i]), visited[0][i] = 1;

	cout << func(N - 1, N - 1);
}