완전탐색

n-1개의 칸막이 후보중에서 m개를 골라야한다. 이진수 비트마스킹을 이용해서 조합을 만들고, preEval[start][end] =( start부터 end를 한그룹으로 볼때 들수 잇는 최대힘)에서 1이 등장시마다 start end를 번갈아 넣어 합을 구한다. 모든 조합 중 최대값을 구한다.

ex. 1010010001 ⇒ preEval[1][3] + preEval[3][6] + preEval[6][10] + preEval[10][11]

물론 시간복잡도때문에 어림도 없다. n^m이면ㅎㅎ

DP

연속된 아이템으로 구간(그룹)으로 나눠야하는 문제유형이다. 이런저런 방법으로 DP 테이블을 구하려고 해봤는데 쉽지 않았다. dpilk] = i번째 목봉을 K에 놓을 때 최대 힘의 값으로 해보려했지만 점화식을 구하지 못했다.( 결국 학회 선배님의 도움을 받아 문제를 풀었다. )

내맘대로 어떻게 DP테이블을 정의하고, 맘대로 세운 테이블의 점화식 관계를 찾는것이 문제였던 것 같다. 결국 DP가 해결해주는건 중복된 부분문제를 메모이제이션으로 연산시간을 줄여주는 것이다.

부분문제를 어떻게 정의할 것인지에 대한 생각없이 물리적인 메모이제이션에 집중한게 화근이었다.

이 문제는 1번~i번 병사가 j개의 그룹으로 나누어질 때, 만들 수 있는 최대 힘을 구하는 것이다.

이를 1번~k번 병사가 j-1개의 그룹으로 나누어질때 만들 수 있는 최대힘으로 나누고, k번~i번 병사는 한 그룹으로 묶어 힘을 평가하면 문제는 쪼개질 수 있다. 그리고 우리는 k가 어디에서 이 값을 최대로 만들어줄지 모르니 k를 1부터 i까지 쭉 돌리면서 최대값을 구하면된다.

code

#include <iostream>
#include <algorithm>
#include <stack>
#include <string.h>
#include <vector>
#include <map>
#include <math.h>
#include <queue>

typedef long long ll;
using namespace std;

ll dp[1001][11]; 
ll h[1001];
ll p[1001];
ll solve(int i, int j){ 
	ll& ret = dp[i][j];
  if(i == 0 ) return 0;
  if(j == 0 ) return -10000000000000000;
  if(ret != -1) return ret;
	ll max_h=0, power=0;
	for(int k = i; k>= j; k--){
		if( h[k] > max_h) {
			max_h = h[k];
			power = p[k];
		}
		else if(h[k] == max_h)power+=p[k]; 
		ret = max(ret, power + solve(k-1, j-1));
	};
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for (int i = 1; i <= n; i++){
        cin>>h[i]>>p[i];
    }
    memset(dp,-1,sizeof(dp));
    solve(n,m);
    cout<<dp[n][m];    
    return 0;
}

중간중간 들었던 의문점이나 포인트

  1. 힘 기준으로 갱신해야하는거 아님?

    반복문을 순회하는 최댓값은 키 기준으로 하는게 맞다. 그룹이 한개일때를 생각해본다면, 우리에겐 더 낮은 병사를 힘이 세다고 고를수 없다는걸 알 수 있다.

  2. TopDown 방식의 구현.

    m명의 병사에 대하여 n 개의 그룹으로 나누는걸 구하기 위해서 (뒤에서 m부터 i까지의 최장신의 힘)과 (i부터 1까지의 group-1로 나눌때 최대의 합의 최대)를 구하면된다.

    Untitled