밀린 에디토리얼 시리즈 5 입니다.
(랭킹 다 찾아볼래면 안드로메다!!!)
Easy(250pt, DiscountCombination)
얼마짜리의 물건을 사고 싶다. 다양한 할인옵션들이 있는데, 이 옵션들은 각각 (추가로 내야 할 금액, 원래 물건이 할인되는 비율) 로 이루어져 있다. 비율이 1, 2, 3% 중 하나로 한정되어 있을 때, 물건을 사기 위해 필요한 최소 가격을 구하여라.
-> 가장 중요한 것은 비율이 1% 2% 3% 중 하나라는 것입니다. 만약 비율이 같은 할인 옵션이라면 당연히 그 중에서 싼 것이 좋겠죠. 따라서 1%짜리 할인옵션을 i개, 2%짜리 할인옵션을 j개, 3%짜리 할인옵션을 k개 사용한다면 1%짜리 할인옵션 중에서 제일 싼 i개 등등을 골라야 할 것입니다. 아래 소스코드는 이를 그대로 옮겨놓은 것입니다.
그냥 무턱대고 모든 경우를 찾는다면 가볍게 시간초과가 될 것입니다.
[spoiler="코드 보기!"]~~~ cpp

#include
#include
#include
#include
#include

Medium(500pt, Chomp)
  Chomp라는 게임은 세로 3줄 가로 N줄의 꽉 찬 테이블에서, 두 명이 턴을 돌아가면서 하는 게임이다. 각 턴에서 플레이어는 남아있는 셀 중 하나를 골라서, 그 셀을 포함하는 오른쪽 위 박스에 있는 모든 셀을 없앤다. 이길 수 있으면 빨리 이기려고, 이길 수 없으면 되도록 늦게 지려고 한다고 할 때, 누가 몇 턴만에 이기는 지 구해라.
  -> 요즘 게임 문제가 많이 나오네요.
  게임의 중간 상태는 항상 (가장 윗줄에 a개, 그 다음 줄에 b개, 마지막 줄에 c개)가 있는 상태라고 나타낼 수 있고, 이 때 각 셀들은 각 줄의 왼쪽에 붙어있게 됩니다. 따라서 table[a][b][c]를 계산한 다음에 table[N][N][N]을 리턴하면 되는 일인데... 부가조건이 있죠. 이길 수 있으면 빨리, 아니면 느리게 게임을 만들어야 합니다. 저는 주어진 대로 1, 2, 3, 4, 5... 를 각각 1턴에 이길 수 있는 경우 등을 나타내게 했고, -1, -2, -3... 을 각각 1턴만에 질 수밖에 없는 경우 등등을 나타내게 했습니다. 이 때 선호도는
  1 > 2 > 3 > 4 > ... > +inf > -inf > ... > -4 > -3 > -2 > -1 이 됩니다.
[spoiler="코드 보기!"]~~~ cpp

#include <vector> 
#include <string> 
#include <queue> 
#include <algorithm> 
#include <map> 
#include <math.h> 
#include <string.h> 
using namespace std; 
int table[101][101][101]; 
class Chomp 
{ 
  public: 
  int moves(int N) 
  { 
    table[0][0][0] = 1; // you will win 
    for (int i=0; i<=N; i++) 
      for (int j=i; j<=N; j++) 
        for (int k=j; k<=N; k++) 
        { 
          if (i+j+k>0) table[i][j][k] = -1; 
          for (int l=0; l<k; l++) 
            for (int m=0; m<3; m++) 
            { 
              if ( m==1 && l>=j ) continue; 
              if ( m==2 && l>=i ) continue; 
              int pick = 0; 
              // (i, j, k), chomp(l, m) 
              if (m==0) 
                pick = table[min(i, l)][min(j, l)][min(k, l)]; 
              if (m==1) 
                pick = table[min(i, l)][min(j, l)][k]; 
              if (m==2) 
                pick = table[min(i, l)][j][k]; 
              if (pick<0) pick = -pick+1; 
              else pick = -pick-1; 
      //        printf("%d %d %d : %d %d : %d\n", i, j, k, l, m, pick); 
              // 1 2 3 4 5 6 7 8 ... +inf -inf ... -8 -7 -6 -5 -4 -3 -2 -1 
              if ( table[i][j][k] < 0 && pick > 0 ) table[i][j][k] = pick; 
              if ( table[i][j][k] > 0 && pick > 0 && table[i][j][k]>pick ) table[i][j][k] = pick; 
              if ( table[i][j][k] < 0 && pick < 0 && table[i][j][k]>pick ) table[i][j][k] = pick; 
            } 
      //    printf("%d %d %d = %d\n", i, j, k, table[i][j][k]); 
        } 
    if ( table[N][N][N] > 0 ) return table[N][N][N]-1; 
    return table[N][N][N]+1; 
  }; 
};

~~~[/spoiler]
Hard(1000pt, BoxFilling)
  주어진 규칙대로 거대한 박스의 각 칸에 번호를 매겨라. 가로 세로 높이가 각각 x y z 인데 여기서 (a,b,c) 셀의 번호는 몇번일까?
  -> 아직 못풀었는데 풀고 올립니다~
<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/45314">원문보기</a>]</div>