DP 공부(1)

 

 

dp가 어려운 나에게 실버 1 dp를 풀어보는것을 시도했다

사실 어렵다기보다는 아이디어는 거의 나오는데 점화식을 못 세우는 기현상이 있었고 티어에 비해 기본기가 많이 부족한 거 같아서 시작..

 

점화식 느낌 잡기 용으로 푼 4문제 정도 가볍게? 정리해본다.

실버 dp였기는 했지만 이전에 구한 상태를 현재 구하고자 하는 값에 반영한다는 느낌을 가지고 문제를 보면 점화식이 쉽게 나왔다.

---

BOJ 15645 - 내려가기 2 , BOJ 2096 - 내려가기

내려가기 2를 풀면 내려가기를 풀 수 있다.

 

다음 칸으로 가는 경우는 바로 아래칸과 인접한 좌 우 칸으로 이동하는 것이다.

그렇다면 i번째 줄에 j번 칸에 올 수 있는 최대 값은 max{i-1번째 줄에서 j번 칸으로 이동 가능한 칸}으로 볼 수 있다.

 

15645 code

int main() {
	fastio;
	int n;
	cin>>n;
	vector<vector<int>>arr(n,vector<int>(3));
	for(auto&v:arr)for(auto&a:v)cin>>a;
	vector<vector<int>>mxdp(n,vector<int>(3,0));
	vector<vector<int>>midp(n,vector<int>(3,0));
	mxdp[0]=arr[0];
	midp[0]=arr[0];
	for(int i=1; i<n; i++){
		mxdp[i][0]=max(mxdp[i-1][0],mxdp[i-1][1])+arr[i][0];
		mxdp[i][1]=max(mxdp[i-1][0],max(mxdp[i-1][1],mxdp[i-1][2]))+arr[i][1];
		mxdp[i][2]=max(mxdp[i-1][1],mxdp[i-1][2])+arr[i][2];
		midp[i][0]=min(midp[i-1][0],midp[i-1][1])+arr[i][0];
		midp[i][1]=min(midp[i-1][0],min(midp[i-1][1],midp[i-1][2]))+arr[i][1];
		midp[i][2]=min(midp[i-1][1],midp[i-1][2])+arr[i][2];
	}
	cout<<max(mxdp[n-1][0],max(mxdp[n-1][1],mxdp[n-1][2]))<<' '<<min(midp[n-1][0],min(midp[n-1][1],midp[n-1][2]));
    return 0;
}

 

내려가기 문제는 메모리 제한이 빡빡하다. 하지만 우리가 구하고자 하는 것은 n번째 줄의 상태정보이다. 

내려가기 2의 코드를 자세히 보면 다음 값을 경신하는 데에 굳이 n칸의 긴 배열을 사용할 필요가 없고 그때그때 갱신해 줘도 된다는 것을 알 수 있다. 

int main() {
    fastio;
    int n;
    cin >> n;
    int arr[3];
    cin >> arr[0] >> arr[1] >> arr[2];
    int adp[3] = { 0, };
    int idp[3] = { 0, };
    adp[0] = idp[0] = arr[0];
    adp[1] = idp[1] = arr[1];
    adp[2] = idp[2] = arr[2];
    int small = 0; int big = 0;
    for (int i = 1; i < n; i++) {
        cin >> arr[0] >> arr[1] >> arr[2];
        int a = adp[0], b = adp[1], c = adp[2];
        adp[0] = max(a, b) + arr[0];
        adp[1] = max(max(a, b), c) + arr[1];
        adp[2] = max(b, c) + arr[2];
        a = idp[0], b = idp[1], c = idp[2];
        idp[0] = min(a, b) + arr[0];
        idp[1] = min(min(a, b), c) + arr[1];
        idp[2] = min(b, c) + arr[2];
    }
    cout << max(max(adp[0], adp[1]), adp[2]) << " " << min(min(idp[0], idp[1]), idp[2]);
    return 0;
}

 

BOJ 22342 - 계산 로봇

 

입력받은 값을 90도 회전시켜서 보면 내려가기처럼 변형하여 풀 수 있다.

$$dp[i][j]=max(dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1])+cost[i][j]$$

i는 90도 회전시켰을 때의 줄, j는 칸으로 본다.

int main() {
	fastio;
	int m,n;
	cin>>m>>n;
	vector<vector<int>>arr(n,vector<int>(m+2,0));
	for(int i=1; i<=m; i++){
		string s;
		cin>>s;
		for(int j=0; j<n; j++)arr[j][i]=s[j]-'0';
	}
	vector<vector<int>>dp(n,vector<int>(m+2,0));
	dp[0]=arr[0];
	for(int i=1; i<n; i++){
		for(int j=1; j<=m; j++){
			dp[i][j]=max(dp[i-1][j],max(dp[i-1][j-1],dp[i-1][j+1]))+arr[i][j];
		}
	}
	int ans=0;
	for(int i=1; i<=m; i++)ans=max(ans,dp[n-1][i]-arr[n-1][i]);
	cout<<ans;
    return 0;
}

 

BOJ 2302 - 극장 좌석

 

vip좌석은 고정이다.

$\prod$ vip좌석들 사이의 경우의 수가 구하고자 하는 값이다.

일반좌석이 연속적으로 배치되어 있을 때 생기는 경우의 수는 피보나치수열임을 알 수 있다.

대충 피보나치 전처리를 해주고 vip좌석 사이의 거리에 해당하는 피보나치 수를 곱해준다.

 

int main() {
	fastio;
	int n,m;
	cin>>n>>m;
	vector<int>arr(m+2,0);
	arr[m+1]=n+1;
	for(int i=1; i<=m; i++){
		cin>>arr[i];
	}
	vector<int>dp(404,0);
	dp[0]=dp[1]=1;
	for(int i=2; i<404; i++)dp[i]=dp[i-1]+dp[i-2];
	int ans=1;
	for(int i=1; i<=m+1; i++){
		ans*=dp[arr[i]-arr[i-1]-1];
	}
	cout<<ans;
    return 0;
}

 

 

---

 

dp 하다 보니 그리디만큼은 아니지만 명확하게 문제를 해결할 수 있는 식이 나온다는 게 재밌었다.