CSES PS - Elevator Rides (bit, dp)

https://cses.fi/problemset/task/1653/

쉬운 설명의 어려운 문제

bit쓰는 dp중엔 기본문제인 듯 하다.

https://suuntree.tistory.com/124?category=797985

비슷한 유형의 더 어려운 문제

 

<문제설명>

최대 20명의 사람들의 몸무게가 주어질 때, 최대 하중이 x인 엘레베이터에 사람을 채워 보내는 최소 운행 횟수를 구해라. (몸무게 <= x)

 

<풀이>

d[i] : 현재 i 사람들이 탔을 때 최소 운행수

f[i] : i 사람들이 탔을 때 마지막 운행 엘레베이터의 몸무게 합.

 

i에 속하지 않는 L에 대해 d[i|(1<<L)]와 f[i|(1<<L)] (i사람들에 L번 사람을 추가하는 경우)를 생각해보자

1) f[i] + w[L] <= x인 경우 마지막 운행에 추가로 L번 사람을 태운다

d[i | (1<<L)] <- d[i]

f[i|(1<<L)] <-  f[i] + w[L]

 

2) 그 외의 경우 마지막 운행에 사람을 태우지 못하므로 새로운 운행을 추가한다.

d[i | (1<<L)] <- d[i]+1

f[i | (1<<L)] <- w[L]

 

=기호 대신 <-기호를 쓴 이유는, d[i | (1<<L)] 에 도달하는 모든 d[i]에 대해 최소값으로 갱신해야 하기 때문이다.

 

f[i]는 d[i]가 갱신될때(혹은 같은값이 들어올때)만 최소값으로 바뀐다. ->코드보면 이해됨

 

예를들어서 상태 111에 도달하는 경우는

011에서 2번 사람을 태우는경우, 101에서 1번사람을 태우는 경우, 110에서 0번사람을 태우는 경우로 다양하다.

(set1 < set2 (포함)인 모든 set1, set2에 대해 set1이 먼저 처리된다.)

 

<코드>

const int MAX = (1 << 20) + 2;
int d[MAX]{ 0 }, f[MAX]{ 0 };
int main() {
	FAST;
	int n, x, w[21]; cin >> n >> x;
	for (int i = 0; i < n; i++) cin >> w[i];

	fill(d, d + MAX, n+1);
	d[0] = 1;

	for (int i = 0; i < (1 << n); i++) {
		for (int l = 0; l < n; l++) {
			if ((i & (1 << l)) == 0) {
				int td, tf;
				if (f[i] + w[l] <= x) {
					td = d[i];
					tf = f[i] + w[l];
				}
				else {
					td = d[i] + 1;
					tf = w[l];
				}
				if (d[i | (1 << l)] == td)
					f[i | (1 << l)] = min(f[i | (1 << l)], tf);
				else if (d[i | (1 << l)] > td) {
					d[i | (1 << l)] = td;
					f[i | (1 << l)] = tf;
				}
			}
		}
	}
	cout << d[(1 << n) - 1] << '\n';
}

 

 

<생각>

책에선 메모이제이션을 pair<int,int> best[i] : { d[i], f[i] }로 했다. 같은 입력에 상태를 두 개갖는 메모이제이션은 처음본다.

 

또한, 현재 인원 s에 대한 dp를 그때그때 하는 식으로, s에 포함된 인원 p에 대해 이 인원 p가 마지막으로 들어오는 상황으로 dp식을 짰다.

 

(책코드)

best[0] = {1,0};
for(int s=1; s<(1<<n); s++){
	//초기값
    best[s] = {n+1, 0};
    for(int p=0; p<n; p++){
    	if(s&(1<<p)){
        	auto option = best[s^(1<<p)];
            if(option.second + w[p] <= x){
            	option.second += w[p];
            }
            else{
            	option.first++;
                option.second = w[p];
            }
            best[s] = min(best[s], option);
        }    
    }
}