백준 6101 식당
https://www.acmicpc.net/problem/6101
간단하지만은 않은 다이나믹 프로그래밍 문제입니다. 저는 먼저 푼 친구가 시간복잡도가 O(n*sqrt(n))으로 풀 수 있다는 것을 알려주었음에도 푸는데 시간이 오래 걸렸어요…
하지만 아이디어에 비해 코드는 간단합니다! 코드를 통해 설명 드리도록 하겠습니다.
#include<bits/stdc++.h>
using namespace std;
const int SZ=205;
int memo[SZ*SZ]; // memoization of minimum cost
int crt_p[SZ*SZ]; // current position of x(or past position)
// let 'number of food types'=A
int first_p[SZ]; // first_p[A]=first position become A
int main(void){
ios::sync_with_stdio(false); cin.tie(NULL);
int n,m; cin>>n>>m;
for(int i=1;i<SZ;i++) first_p[i]=1;
for(int i=1;i<=n;i++) memo[i]=SZ*SZ;
for(int i=1;i<=n;i++){
int x; cin>>x;
int nn=(int)sqrt(n);
for(int j=nn;j>=2;j--){
if(crt_p[x]<first_p[j]) first_p[j]=first_p[j-1];
}
if(crt_p[x]!=i-1) first_p[1]=i;
crt_p[x]=i;
for(int j=1;j<=nn;j++){
memo[i]=min(memo[i],memo[first_p[j]-1]+j*j);
}
}
cout<<memo[n];
return 0;
}
배열 설명
memo[n]: 1~n번째 염소를 그룹화 하는데 드는 최소 비용
crt_p[n]: 음식 n을 원했던 가장 최근 염소
first_p[n]: 특정 위치 x에서 출발하여 음식 집합의 크기가 n이 되는 가장 숫자가 작은 염소
이 풀이의 핵심은
첫째, 존재하는 모든 그룹의 크기가 sqrt(n)보다 작고,
만약 sqrt(n)보다 큰 그룹이 있다면 비용이 반드시 n보다 크게 됩니다! 하나씩 묶는 것보다 비용이 커지게 되죠.
for(int i=1;i<=n;i++){
for(int j=1;j<=sqrt(n);j++){
memo[i]=min(memo[i],memo[first_p[j]-1]+j*j);
}
}
// 현재 first_p[j]는 n에서부터 시작하여 집합의 크기가 j가 되는 가장 작은 위치입니다.
// first_p만 어떻게 잘 하면 되겠군요.
둘째, first_p 배열을 채우는 데 O(1)의 시간복잡도만이 필요하다는 점입니다.
first_p를 이차원 배열로 정의했다면 first_p[x+1][n]을 first_p[x][n]에 관련된 식으로 나타낼 수 있습니다. 하지만 이를 이차원 배열에 전부 저장할 필요는 없습니다. first_p[x-1][n],first_p[x-2][n] … 는 사용하지 않기 때문이죠.
if(crt_p[new_cow]<first_p[x-1][n]) first_p[x][n]=first_p[x-1][n-1]
else first_p[x][n]=first_p[x-1][n]
//이라는 점화식을
if(crt_p[new_cow]<first_p[n]) first_p[n]=first_p[n-1]
//한 줄로 고칠 수 있습니다.(지금 보니 2차원 배열로 짜는게 이해하기 더 쉬웠겠네요)
나머지 코드는 단순 초기화 과정입니다! 끝!!
