반응이 좋아서 또 써봅니다.

2문제 이상 풀면 꽤나 높은 등수였고, 하나만 빨리 풀어도 100등 이내에 들 수 있었던 셋이었네요.

Easy (250 pts.)

• 문제 설명 여러개의 크레인과 상자가 있습니다. 크레인으로 상자를 모두 옮기려고 합니다. 크레인과 상자의 각각 무게가 주어집니다. 크레인의 무게가 상자의 무게 이상일 때만, 크레인이 상자를 옮길 수 있습니다. 한 크레인은 한 상자를 옮기는데 1의 시간이 걸리고, 모든 크레인은 쉼없이 일합니다. 모든 상자를 다 옮기는 데 걸리는 최소 시간을 구하세요. [spoiler="더 보기..."] * 풀이 t라는 시간이 가능하다면, 당연히 t+1시간에도 모든 상자를 옮기는 게 가능하기 때문에 이분검색으로 답을 정하여, 풀 수 있습니다. 답을 정하고나면, 그 답이 가능한지 검사하는 건 쉽습니다. 답을 t로 정했다면, 가장 무거운 상자 t개는 가장 무거운 크레인이 옮기고, 그 다음으로 무거운 상자 t개는 두번째로 무거운 크레인이 옮기고, 그 다음 t개는 세번째... 이런 식으로 하시면 됩니다. 답은 최소 (t*크레인 수 >= 상자 수) 조건이 만족하는 t값부터 가능합니다. [code] typedef vector VI; #define PB push_back #define REP(i,n) for(int i=0; i<(n); ++i) #define ALL(X) (X).begin(),(X).end() #define SZ(X) (int)(X).size() #define FORE(it,X) for(__typeof((X).begin()) it=(X).begin(); it!=(X).end(); ++it) class ShipLoading { public: int minimumTime(vector , vector ); }; int ShipLoading::minimumTime(vector cr, vector boxes) { string b; FORE(it,boxes) b+=*it; VI dt; istringstream in(b); int a; while (in>>a) dt.PB(a); sort(ALL(cr)); sort(ALL(dt)); reverse(ALL(cr)); reverse(ALL(dt)); int l=1,r=2500,m,dp=-1; while (l*SZ(cr)cr[k]) { no=1; break; } } if (no) l=m+1; else { dp=m; r=m-1; } } return dp; } [/code] [/spoiler] [spoiler="더 보기..."] * 풀이 문제만 보면 완벽하게 0-1 냅색 문제입니다. 그런데 문제는 제한 조건이 너무 크다는 데에 있습니다. 보통 0-1 냅색 문제는 dy[i][j] = i번째 우표까지 j원을 썼을 때, 얻을 수 있는 최대 가치. 이렇게 정의되는데요. 이 문제에서 우표의 개수는 최대 32이지만, 각 우표의 가격이 최대 3천만이나 됩니다. 그렇다면 저런 식으로 풀자면 dy[32][30000000*32]의 메모리를 잡아야 하는데, 당연히 불가능하겠죠. 그렇다면 개수가 32개밖에 안 되니까 2^32의 경우를 모두 보는 고려해보는 건 어떨까요? 이것도 역시 안됩니다. 2^32는 너무 크죠. 42억 가지를 고려하기엔 컴퓨터가 너무 느립니다. 그래서 제가 쓴 방법은 이 2가지를 적절히 섞은 방법입니다. 우선 n개의 우표를 반으로 나눠서 A그룹, B그룹으로 나눕니다. 그래서 각각 2^(n/2)의 경우를 모두 고려해서 배열(da, db)에 (가격(cost), 가치(value))를 저장합니다. 그리고 각각 그룹을 가치 순으로 정렬합니다. 그리고나서 가치가 높은 것부터 보면서 DP를 적용합니다. da[i].cost = da[i].value 이상의 가치를 만들 때 필요한 최소한의 가격. da[i].cost = min(da[i].cost, da[i+1].cost) // 더 높은 가치를 만드는데 더 낮은 가격이 가능하다면... DP를 적용한 후에는 간단합니다. A그룹에서 가능한 모든 경우를 보면서 K가치를 만드는데 필요한 최소한의 cost를 B그룹에서 찾아주며 답을 갱신하면 됩니다. 가치 순으로 정렬이 되어 있으니 이분검색으로 찾는 게 가능하겠죠. 그래서 O( 2^(n/2) * log(2^(n/2)) ) 다시 쓰자면 O( 2^(n/2) * n ) 정도가 되겠네요. 아 그리고, 처음에 가지고 있던 우표는 전부 돈으로 바꿨다고 치면, 마지막에 구한 답에서 그 돈을 빼주면 되겠죠? (그래서 음수가 된다면 이미 K가치 이상 가졌다는 뜻이죠.) [code] typedef long long LL; typedef long double LD; typedef vector VI; typedef pair PII; typedef vector VPII; #define MP make_pair #define ST first #define ND second #define PB push_back #define FOR(i,a,b) for( int i=(a); i<(b); ++i) #define FORD(i,a,b) for( int i=(a); i>(b); --i) #define REP(i,n) for(int i=0; i<(n); ++i) #define ALL(X) (X).begin(),(X).end() #define SZ(X) (int)(X).size() #define FORE(it,X) for(__typeof((X).begin()) it=(X).begin(); it!=(X).end(); ++it) struct ele { int v,c; bool operator <(ele t) const { if (v==t.v) return c>t.c; // 가치가 같을 때는 가격이 큰 게 앞에 오도록.. return v, vector , vector , int); }; int CollectingPostmarks::amountOfMoney(vector pr, vector ha, vector va, int K) { int ini=0; REP(i,SZ(ha)) ini+=pr[ha[i]]; // 처음 가지고 있던 우표는 모두 돈으로 바꾼다. int n=SZ(pr); vector da,db; REP(i,1<<(n/2)) { // A그룹 저장 ele tmp; tmp.c=tmp.v=0; REP(j,n/2) if (i&(1<#define MP make_pair  
• #define X first  
• #define Y second  
• #define PB push_back  
• #define FOR(i,a,b) for( int i=(a); i<(b); ++i)  
• #define REP(i,n) for(int i=0; i<(n); ++i)  
• #define ALL(X) (X).begin(),(X).end()  
• #define SZ(X) (int)(X).size()  
• #define FORE(it,X) for(__typeof((X).begin()) it=(X).begin(); it!=(X).end(); ++it)  
•    
• class HoleCakeCuts {  
• public:  
•   int cutTheCake(int, int, vector <int>, vector <int>);  
• };  
•    
• int hy[4]={0,0,-1,1};  
• int hx[4]={-1,1,0,0};  
• int chk[205][205];  
• int go[205][205];  
• int cakl;  
•    
• void bfs(int x,int y)  
• {  
•   queue<PII> q;  
•     
•   chk[x][y]=1;  
•   q.push(MP(x,y));  
•   while (!q.emptyempty()) {  
•     PII ka=q.front(); q.pop();  
•     x=ka.X,y=ka.Y;  
•       
•     REP(i,4) {  
•       int py,px;  
•       px=x+hx[i];  
•       py=y+hy[i];  
•       if (go[x][y]&(1<<i)) continue;  
•       if (px<0 || px>=cakl*2) continue;  
•       if (py<0 || py>=cakl*2) continue;  
•       if (chk[px][py]) continue;  
•       chk[px][py]=1;  
•       q.push(MP(px,py));  
•     }  
•   }  
• }  
•    
• int HoleCakeCuts::cutTheCake(int ca, int hole, vector <int> ycut, vector <int> xcut) {  
•   cakl=ca;  
•   memset(chk,0,sizeof(chk));  
•   memset(go,0,sizeof(go));  
•   FOR(i,-hole+cakl,hole+cakl)  
•   FOR(j,-hole+cakl,hole+cakl)  
•     chk[i][j]=1;  
•   REP(i,SZ(ycut)) {  
•     int y=ycut[i]+cakl;  
•     REP(j,cakl*2+1) {  
•       go[j][y-1]^=8;  
•       go[j][y]^=4;  
•     }  
•   }  
•   REP(i,SZ(xcut)) {  
•     int x=xcut[i]+cakl;  
•     REP(j,cakl*2+1) {  
•       go[x-1][j]^=2;  
•       go[x][j]^=1;  
•     }  
•   }  
•     
•   int dp=0;  
•   REP(i,cakl*2)  
•   REP(j,cakl*2)  
•     if (chk[i][j]==0) {  
•       dp++;  
•       bfs(i,j);  
•     }  
•   return dp;  
• }  
#define MP make_pair #define X first #define Y second #define PB push_back #define FOR(i,a,b) for( int i=(a); i<(b); ++i) #define REP(i,n) for(int i=0; i<(n); ++i) #define ALL(X) (X).begin(),(X).end() #define SZ(X) (int)(X).size() #define FORE(it,X) for(__typeof((X).begin()) it=(X).begin(); it!=(X).end(); ++it) class HoleCakeCuts { public: int cutTheCake(int, int, vector , vector ); }; int hy[4]={0,0,-1,1}; int hx[4]={-1,1,0,0}; int chk[205][205]; int go[205][205]; int cakl; void bfs(int x,int y) { queue q; chk[x][y]=1; q.push(MP(x,y)); while (!q.empty()) { PII ka=q.front(); q.pop(); x=ka.X,y=ka.Y; REP(i,4) { int py,px; px=x+hx[i]; py=y+hy[i]; if (go[x][y]&(1<=cakl*2) continue; if (py<0 || py>=cakl*2) continue; if (chk[px][py]) continue; chk[px][py]=1; q.push(MP(px,py)); } } } int HoleCakeCuts::cutTheCake(int ca, int hole, vector ycut, vector xcut) { cakl=ca; memset(chk,0,sizeof(chk)); memset(go,0,sizeof(go)); FOR(i,-hole+cakl,hole+cakl) FOR(j,-hole+cakl,hole+cakl) chk[i][j]=1; REP(i,SZ(ycut)) { int y=ycut[i]+cakl; REP(j,cakl*2+1) { go[j][y-1]^=8; go[j][y]^=4; } } REP(i,SZ(xcut)) { int x=xcut[i]+cakl; REP(j,cakl*2+1) { go[x-1][j]^=2; go[x][j]^=1; } } int dp=0; REP(i,cakl*2) REP(j,cakl*2) if (chk[i][j]==0) { dp++; bfs(i,j); } return dp; }

그런데 다른 해법도 존재했습니다. 저랑 같은 방에서 하던 _Romka_라는 분의 해법인데요.
저는 처음에 DFS나 BFS가 정해라고 생각하고, "뭐야, 이거 당연히 안 되겠지~"
이러면서 첼린지를 했는데, 바로 실패해서, 더이상 첼린지는 안 하고 sys test만 기다렸습니다.
근데 sys test 끝나고보니, 이 코드가 통과하더군요.
어떤 방법인지는 각자의 숙제로 남길게요 >_<
view plainprint?