[ BOJ 백준 1126번 - 같은 탑] 해설 및 코드

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

 

목적

N개의 블록을 이용해 두 탑의 높이를 같도록 쌓는 여러가지 방법 중, 최대 높이를 구하자.

 

접근법

1. 두 탑의 높이 차를 이용한 DP를 사용하자. 

 

2. s[i][j]를 i번째 블럭을 이용해 높이차가 j인 두개의 탑을 쌓았을 때의 최대 높이라고 정의한다.

• 예를 들어, i번째 블럭을 이용해 높이 차가 5이 두 탑을 쌓았다고 가정하겠다.
• 그러면 왼쪽 탑이 높든 오른쪽 탑이 높든 높이 차 j라는 하나의 경우로 처리할 수 있다.
• 또한, 탑의 높이를 [L, R]와 같이 표현하면, [10, 15]나 [25, 20]를 s[i][5]=25 라는 값으로 처리할 수 있다.

3. i+1번째 블럭을 이용하는 경우는 어떻게 처리하나? 각 j의 값에 따라 세 가지 경우가 있다. (코드의 주석 각각이 다음에 해당한다.)

• 블럭을 사용하지 않는 경우
• 높이 차를 크게 하는 경우
• 높이 차를 작게 하는 경우

4. 마지막으로, 모든 블럭의 높이 합은 5*10^5을 넘지 않으므로 높이 차도 이 값의 절반을 넘지는 않을 것이다.

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
#define update(a,b) a=max(a,b)
using namespace std;

const int MAXH=25e4;
int n,h,s[2][MAXH+1],val,i;

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

	memset(s,-1,sizeof(s));
	s[0][0]=0;

	cin>>n;
	while(n--){
		cin>>h;
		int ni=i^1;
		f(j,0,MAXH)if((val=s[i][j])>=0){
			int a=j+h,b=abs(j-h);
			update(s[ni][j],val);				// 1
			if(a<=MAXH)update(s[ni][a],val+h);		// 2
			if(b<=MAXH)update(s[ni][b],val+(j<h?b:0));	// 3
		}
		i=ni;
	}

	cout<<(s[i][0]>0?s[i][0]:-1);
	return 0;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.