겨울방학 SRM 모임 연습으로, JongMan, domeng, altertain, ryuwonha, xhae 다섯 명이 참가했습니다. 
노가다 구현 500 과 후덜덜한 기하 1000, 그리고 노가다나 적절한 센스로 풀리는 250 으로 구성된 셋이었고요. 결과는 http://spreadsheets.google.com/pub?key=prOLhYJ-PdsL_svuPcyB3Pw&gid=0 에서 볼 수 있습니다. (태윤님 근데 저 M 좀 대문자로 바꿔주세요.. -_-)
250 - ElevatorLimit 
Key Insight
physicalLimit * n <= 5000
해법
모든 문제에서 가장 먼저 확인해야 할 것은, 가장 무식한 방법으로도 문제를 풀 수 있는가입니다. 시간 안에만 들어간다면, 가장 무식하고 가장 작성하기 편한 해법이 가장 좋은 해법이죠. ^^ 그래서, 처음에 0 명이 있었을 경우부터 physicalLimit 명이 있었을 경우까지의 모든 시나리오를 모두 시뮬레이션하면서 오류가 있는 경우를 제외하면 쉽게 답을 구할 수 있습니다.
오류가 있는 경우란: exit[i] 명이 나갔는데 엘리베이터에 음수명이 있을 경우와, enter[i] 명이 탔는데 physicalLimit 명을 초과하는 경우겠지요.
그 외 O(n) 해법도 있습니다. 처음에 0 명이 있다고 가정하고 쭉 시뮬레이션을 한 뒤 (오류 무시하고) 한 시점에 엘리베이터에 있었던 최소 인원수 A 와 최대 인원수 B 를 각각 기록합니다. 그러면, A <= 0 이겠는데, 이 때 처음 엘리베이터에서는 -A 명에서 physicalLimit - B 명까지 존재할 수 있었겠죠. 물론, 이 때는 각종 예외들을 처리해 줘야 하므로 검증이 좀 더 어렵다는 문제가 있죠. (실제로 r모 레드님은 이걸로 챌린지.)
소스코드 나갑니다.

struct ElevatorLimit 
{
  vector  getRange(vector  enter, vector  exit, int physicalLimit) 
  {
    int mini = physicalLimit + 1;
    int maxi = -1;
    for(int begin = 0; begin <= physicalLimit; ++begin)
    {
      int current = begin;
      bool valid = true;
      for(int i = 0; i < enter.size(); ++i)
      {
        if(current < exit[i]) { valid = false; break; }
        current -= exit[i];
        current += enter[i];
        if(current > physicalLimit) { valid = false; break; }
      }
      if(valid)
      {
        mini = min(mini, begin);
        maxi = begin;
      }
    }
    if(maxi == -1) return vector();
    vector ret(2);
    ret[0] = mini;
    ret[1] = maxi;
    return ret;
  }
};

500 - RPGRobot
아, 문제 조낸 기네여.. 사실 알고 보면 문제는 단순합니다.
Key Insight
width * height * length(moves) 해봐야 얼마 안되는구나.
해법
넵 역시 닥치고 시뮬레이션입니다. 가장 간단한 방법은 각 위치에 대해서 이 위치에서 주어진 movement 를 할 수 있나 같은 함수를 만들어서 순서대로 호출하는 겁니다. 그 안에선 간단한 시뮬레이션을 하면서 현재 위치의 상하좌우에 벽이 있는지 여부가 기록과 맞는지를 비교하면 되죠.
큐를 만들어서 모든 초기상태를 집어넣고, 큐가 빌 때까지 탐색한다 (altertain, ryuwonha) .. 이런 것도 때깔나지만 좀 오버킬이라고 할 수 있습니다.
그 외 파싱도 좀 귀찮습니다. 이런 데서는 깔끔하게 짜는 능력이 다른 무엇보다 중요하죠. 자기가 작성한 코드가 한 번에 동작할 수 있도록 연습하는 게 좋겠네연. 'ㅅ'
제 코드 나갑니다. (출력 순서를 y좌표-x좌표로 해서 틀린 비운의..)

struct RPGRobot 
{
  int width, height;
  vector m;
  void assertWall(int y, int x, bool isWall)
  {
    if(y < 0 || x < 0 || y >= m.size() || x >= m[0].size()) return;
    bool itsWall = (m[y][x] != ' ');
    if(itsWall != isWall) throw 1;
  }
  bool isValid(int y, int x, const vector >& mv)
  {
    try
    {
      for(int i = 0; i < mv.size(); ++i)
      {
        assertWall(y*2+1-1, x*2+1  , count(all(mv[i].first), 'N') == 0);
        assertWall(y*2+1+1, x*2+1  , count(all(mv[i].first), 'S') == 0);
        assertWall(y*2+1  , x*2+1+1, count(all(mv[i].first), 'E') == 0);
        assertWall(y*2+1  , x*2+1-1, count(all(mv[i].first), 'W') == 0);
        char dir = mv[i].second[0];
        if(dir == 'N') --y;
        if(dir == 'S') ++y;
        if(dir == 'E') ++x;
        if(dir == 'W') --x;
      }
    }
    catch(int x)
    {
      return false;
    }
    return true;
  }
  vector  where(vector  map, string movements) 
  {
    m = map;
    height = m.size() / 2;
    width = m[0].size() / 2;
    vector > mv;
    istringstream inp(movements);
    string tok;
    while(inp >> tok)
    {
      tok += ",-";
      replace(tok.begin(), tok.end(), ',', ' ');
      istringstream inp2(tok);
      string first, second;
      inp2 >> first >> second;
      mv.push_back(make_pair(first, second));
    }
    vector ret;
    for(int j = 0; j < width; ++j)
    for(int i = 0; i < height; ++i)
      if(isValid(i, j, mv))
      {
        char buf[64];
        sprintf(buf, "%d,%d", 2*j+1, 2*i+1);
        ret.pb(buf);
      }
    return ret;
  }
};

1000 - DogWoods
아 문제 완전 안드로 -_-;;; 딴 거 볼 것 없이 1번 예제에 딸려오는 그림을 보시면 문제가 이해가 갈 겁니다.
Key Insight
볼 거 없이 시뮬레이션이구나
해법
넵 역시 닥치고 시뮬레이션 + 기하입니다. 이 셋 세터가 누군지.. 하악 어쨌든 적절한 가정과 코딩을 통해서 해야 하는 코딩의 양을 많이 줄일 수 있습니다. 일단, 원점을 중심으로 하는 원과 다른 원의 교차점을 구하는 식이 주어진다는 것은 좀 다행이죠. 이걸 이용해서 시뮬레이션을 하려면 다음과 같은 단계가 필요할 겁니다.

• R = 현재 위치와 원점과의 거리
• 원점을 중심으로 하고 반지름이 R 인 원과 교차하는 모든 나무들을 찾는다
  • 없으면 -1 리턴
• 시계 방향으로 달렸을 때 처음 만나는 점을 찾는다
• 이 나무를 타고 반시계 방향으로 내려갈 것인데
  • 이 나무가 원점을 중심으로 하고 반지름이 10 인 원과 교차한다면, 반시계 방향으로 달리다 숲의 중심에 도달
  • 안 교차 한다면, 원점과 가장 가까운 점까지 달려내려간 후 맨 위로 돌아감 하악.. 뭐 말이 쉽지 좀 안드로메다죠. 적절한 코딩을 통해서 이 모든 것을 극복해야 합니다. 이런 경우 효율적으로 코딩을 하려면 점이나 원 등의 기본적인 primitive 들을 클래스화하는 것이 좋습니다. 예를 들어, 내가 나무 A 에 부딪혀서 원점과 가장 가까운 점까지 달려내려가려는데, 이 점의 위치를 구한다고 합시다. 덧셈, 뺄셈, 곱셈과 길이 구하기 등이 적절히 구현된 벡터 클래스를 가지고 있다면 double a = A.center().norm(); // 원점에서 A의 중심까지의 거리 double b = A - A.radius();    // 원점에서 우리가 찾는 점까지의 거리 return A.center() * (b / a); 로 (비교적) 간단하게 이 일을 할 수가 있겠죠. 그 외에 구현이 번거로운 점은 시계 방향으로 달렸을 때 처음 만나는 점 구하기 정도인데요. 모든 후보를 구한 뒤, atan2() 함수를 이용해 현재 점부터 그 점까지 가기 위한 각도를 구해서 최소를 구하면 비교적 편하게 할 수 있었던 것 같네요. 이것은 "구현하는" 문제라, 가장 짧게 코드를 짜는 연습을 해 보는 데 좋을 것 같습니다. :-) 깔끔한 코드 짜게 되면 올려 주세요~ 제 코드 나갑니다. ~~~ cpp const double EPS = 1e-7; const double PI = 2.0 * acos(0.0); struct Point { double y, x; Point(double y = 0, double x = 0) : y(y), x(x) {} Point operator - (const Point& rhs) const { return Point(y - rhs.y, x - rhs.x); } Point operator * (double rhs) const { return Point(y * rhs, x * rhs); } double norm() const { return hypot(y, x); } double degree() const { double t = atan2(y, x); if(t < 0) t += 2 * PI; return t; } }; struct Circle { double y, x, rad; Circle(double y = 0, double x = 0, double rad = 0) : y(y), x(x), rad(rad) {} Point center() const { return Point(y, x); } }; inline double sqr(double x) { return x*x; } struct DogWoods { vector C; vector circleIntersection(double r1, const Circle& c) { double x0 = c.x, y0 = c.y, r0 = c.rad; vector ret; double D = c.center().norm(); if(D > r1 + r0 - EPS) return ret; // reject no/one intersection if(D + r0 + EPS < r1) return ret; // no intersection double x, y, d, p; d = sqr(x0) + sqr(y0);
    p = sqrt(( sqr(r0+r1) - d) * (d - sqr(r1-r0))); x = x0 / 2 - x0 * (sqr(r0) - sqr(r1)) / (2*d) + y0 * p / (2*d); y = y0 / 2 - y0 * (sqr(r0) - sqr(r1)) / (2*d) - x0 * p / (2*d); ret.push_back(Point(y, x)); x = x0 / 2 - x0 * (sqr(r0) - sqr(r1)) / (2*d) - y0 * p / (2*d); y = y0 / 2 - y0 * (sqr(r0) - sqr(r1)) / (2*d) + x0 * p / (2*d); ret.push_back(Point(y, x)); return ret; } double degreeBetween(const Point& a, const Point& b) { double thetaA = a.degree(); double thetaB = b.degree(); double diff = thetaA - thetaB; if(diff < 0) return diff + 2 * PI; return diff; } double howFar(vector x, vector y, vector diameter, int startx, int starty) { for(int i = 0; i < x.size(); ++i) C.push_back(Circle(y[i], x[i], diameter[i] / 2.0)); Point here(starty, startx); if(here.norm() <= 10) return 0; double run = 0; while(true) { double R = here.norm(); // get all colliding points vector > collide; for(int i = 0; i < C.size(); ++i) { vector p = circleIntersection(R, C[i]); for(int j = 0; j < p.size(); ++j) collide.push_back(make_pair(p[j], i)); } if(collide.empty()) return -1; // ooops // get the nearest colliding point int best = 0; double bestMove = degreeBetween(here, collide[0].first); for(int i = 1; i < collide.size(); ++i) { double candMove = degreeBetween(here, collide[i].first); if(candMove < bestMove) { bestMove = candMove; best = i; } } run += bestMove * R; here = collide[best].first; int circle = collide[best].second; vector p = circleIntersection(10, C[circle]); if(!p.empty()) { // yay, finally Point arrival = p[0]; if((here-p[0]).norm() > (here-p[1]).norm()) arrival = p[1]; double theta = degreeBetween(arrival - C[circle].center(), here - C[circle].center()); run += theta * C[circle].rad; break; } else { double D = C[circle].center().norm(); Point arrival = C[circle].center() * ((D - C[circle].rad) / D); double theta = degreeBetween(arrival - C[circle].center(), here - C[circle].center()); run += theta * C[circle].rad; here = arrival; } } return run; } }; ~~~
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]