재밌는 퀴즈 몇개

웹 서핑을 하다가 우연히 Sample Interview Questions라는 페이지를 찾았는데 제목은 뭔가 이상하지만 결국은 재밌는 퀴즈들이 모여있는 페이지입니다.
오랫만에 머리를 써보자 생각하고 몇 문제 풀어보았는데 재밌네요!! ;)

앞에서부터 풀고 있는데 한번 시간되면 풀어보세요.

1. 사각형의 케잌안에 사각형 모양의 구멍이 있습니다. 이 구멍의 크기나 각도는 어떻게 되어 있더라고 상관없습니다. 한칼에 이 남은 케잌을 정확히 이등분하려면 어떻게 잘라야 할까요?
2. 정수로 이루어진 배열이 있습니다. 이 배열의 sub 배열중 최대값을 가지는 sub 배열을 O(N) 의 복잡도로 찾는 프로그램을 작성하세요.
   - 배열: 93 5 42 -68 -91 56 -93 5 80 92
   - 정답: [7, 9] = 5 + 80 + 92 = 177
3. 네명의 사람이 다리의 한쪽에 있습니다. 이 다리는 한번에 최대 두명만 건널 수 있으며 건너는 사람들은 반드시 손전등을 가지고 있어야 합니다. (밤이랍니다.그리고 당근 손전등은 한개입니다.) 단 각 사람이 다리를 건너는데 걸리는 시간은 사람에 따라 다르며 두명이 건널때는 둘 중 느린 사람의 속도에 맞추어야 합니다. 각 사람의 속도가 다음과 같을 때 17분만에 모든 사람이 건널 수 있는 방법을 찾으세요.
   - 사람1: 건너는데 1분
   - 사람2: 건너는데 2분
   - 사람3: 건너는데 5분
   - 사람4: 건너는데 10분

두번째 문제의 답만 빼고는 해당 페이지에 답이 있습니다. 제가 작성한 두번째 문제의 답은 내일 올려보겠습니다. :-)

원문

1. Given a rectangular (cuboidal for the puritans) cake with a rectangular piece removed (any size or orientation), how would you cut the remainder of the cake into two equal halves with one straight cut of a knife ?
2. You're given an array containing both positive and negative integers and required to find the subarray with the largest sum (O(N) a la KBL). Write a routine in C for the above.
3. There are 4 men who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each man walks at a different speed. A pair must walk together at the rate of the slower mans pace.
   - Man 1:1 minute to cross
   - Man 2: 2 minutes to cross
   - Man 3: 5 minutes to cross
   - Man 4: 10 minutes to cross

2번 정답

제가 C++로 작성해봤습니다. 더 간단한 방법이 있을지도 모르겠습니다. :-)

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <boost/lambda.hpp>
#include <boost/bind.hpp>

using namespace std;
using namespace boost::lambda;

int main()
{
  srand(time(0));

  const int SIZE = 10;

  vector<int> data(SIZE);

  // use random sequence
  for_each(data.begin(), data.end(), _1 += bind(rand) % 200 - 100);

  // use hand-made test sequence
  /*
  //istringstream test("-38 66 -49 -38 78 84 49 -83 -88 32"); // [4, 6] = 211
  //istringstream test("2 -5 3 7 -9 5 3 8 -20 10"); // [2, 7] = 17
  istringstream test("93 5 42 -68 -91 56 -93 5 80 92"); // [7, 9] = 177
  for_each(data.begin(), data.end(), test >> _1);
  */

  for_each(data.begin(), data.end(), cout << _1 << ' ');
  cout << '\n';

  int end = 0;
  int maxval = data[0];
  int curr = data[0];

  for (int i = 1; i < SIZE; ++i) {
    curr += data[i];
    if (curr < data[i]) {
      curr = data[i];
    }
    if (maxval < curr) {
      maxval = curr;
      end = i;
    }
  }

  curr = maxval;
  int start = 0;
  for (start = end; curr != 0; --start) {
    curr -= data[start];
  }
  ++start;

  cout << "[" << start << ", " << end << "] = " << maxval << endl;
}