글 읽기 - 메모리제이션 흰트좀 주십시요 ㅠㅠ

nlkey2022 4년 전 0

메모리제이션 흰트좀 주십시요 ㅠㅠ

유니크한 key를 못찾겠네요 ㅠㅠ

일단 당직 스면서 좀 더 생각해보겠습니다!!

#include<bits/stdc++.h>
using namespace std;
int a[2001], b[2001];
int d[2001][2001][4];
int n; 
// s->1, u->2, d->3
int go(int up, int down, int sum, int mode){
	if(up == n && down == n) return d[up][down][mode] = sum;
	else if(up == n && down != n){
		for(int i=down+1; i<=n; i++)
			sum += pow(a[up]-b[i],2);
		return d[up][down][mode] = sum;
	}else if(up != n && down == n){
		for(int i=up+1; i<=n; i++)
			sum += pow(a[i]-b[down],2);
		return d[up][down][mode] = sum;
	}
	//if(d[up][down][mode] != 0) return d[up][down][mode];
	int res = INT32_MAX;
	if(mode == 1){
		res = min(res, go(up+1,down+1, sum + pow(a[up+1]-b[down+1],2), 1));
		res = min(res, go(up+1,down, sum + pow(a[up+1]-b[down],2), 2));
		res = min(res, go(up,down+1, sum + pow(a[up]-b[down+1],2), 3));
	}else if(mode == 2){
		res = min(res, go(up+1,down+1, sum + pow(a[up+1]-b[down+1],2), 1));
		res = min(res, go(up+1,down, sum + pow(a[up+1]-b[down],2), 2));
	}else if(mode == 3){
		res = min(res, go(up+1,down+1, sum + pow(a[up+1]-b[down+1],2), 1));
		res = min(res, go(up,down+1, sum + pow(a[up]-b[down+1],2), 3));
	}
	return d[up][down][mode] = res;
}
int main(){
	cin >> n;
	for(int i=1; i<=n; i++) cin >> a[i];
	for(int i=1; i<=n; i++) cin >> b[i];
	
	cout << go(1,1, pow(a[1]-b[1],2), 1);
}

Green55 4년 전 1

mode의 역할이 무엇인지 모르겠습니다. up과 down이 같다면 부분 문제를 푸는 방법이 다를 이유가 없습니다.

nlkey2022 4년 전 0

ssangba55

bottom-up에서 top-down 방식으로 메모리제이션으로 하니 맞았습니다!!

mode의 역할은 다음과 같습니다.

1 -> up과 down이 모두 1씩 감소함

2 -> up만 1감소하고 down은 그대로

3 -> down만 1감소하고 up은 그대로

int go(int up, int down,int mode){
    
}
int main(){
	cin >> n;
	for(int i=1; i<=n; i++) cin >> a[i];
	for(int i=1; i<=n; i++) cin >> b[i];
	memset(d,-1,sizeof(d));
	cout << go(n,n,1);
}

nlkey2022 4년 전 0

이렇게 나누는 이유는 mode 2와 3일때 경우의수를 줄이기 위함입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리제이션 흰트좀 주십시요 ㅠㅠ

nlkey2022 4년 전 0

Green55 4년 전 1

nlkey2022 4년 전 0

nlkey2022 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말