오랜만에 Div1에서 했다.. 공포의 아침 11시 타임..;; 게다가 첫번째 문제도 250이 아닌 300 .. -_-;; 분위기는 완전 Div2 복귀였는데.. 그럭저럭 선방해서 rating도 올리고 Div1을 유지했다..

방 11등 전체 287등..

사용자 삽입 이미지
녹색과 회색들만보다가 파랑과 노랭이들이 있으니 좀 어색하군..;; 왠지 압도당하는 느낌.. ㄷㄷㄷ



[300] MarblesRegroupingEasy
2차원 배열이 주어지고.. (i, j)은 i박스의 j색깔의 구슬의 개수를 의미한다.. 하나의 박스는 joker라고해서 여러가지 색깔의 구슬을 다 가질수 있고.. 나머지박스는 한가지 색깔의 구슬만 가지고 있어야한다.. 그리고 같은색깔의 구슬은 joker를 제외하고 나누어져있으면 안된다.. 이러한 조건을 만족시키도록 구슬을 옮길때 최소 몇번의 move가 필요한지 구하는 문제.. 임의의 박스에서 색깔에관계없이 임의의 구슬의 개수를 옮기는데 드는 비용은 1이다..

처음에 문제를 잘못이해하고 안드로까지 갔다가 다시 돌아왔다.. 흠.. 한 박스에서 한가지 색깔의 구슬을 임의의개수 옮기는데 비용이 1인줄 알고 다짰는데.. 샘플이 안나와서 당황.. -_-;; 문제를 다시보고 패닉상태에 빠지면서 좌절했다.. 다 포기하는 심정으로.. 그냥 주식이나 보고있었는데 막판에 번뜩 떠올라 잽싸게 코딩했다.. 300점짜리를 110점 먹었다.. -_-;;

일단 각 box에 대해서 joker라고 가정하고 나머지를 체크한다.. joker가 아닌 box에 대해서 두가지 이상의 구슬로 채워져있으면.. 무조건 한번 옮겨야한다.. (그냥 다 joker로 옮기면 된다..) 한가지 구슬로만 채워져있는경우.. 다른박스중에 역시 한가지색깔로 이루어져있고 그게 같은 색일경우면 역시 이동해야하고 그렇게 겹치는 경우가 없으면.. 이동할 필요가 없다..

으.. 여러모로 짜증났던 문제.. 그래도 이 문제가 Div1 첫번째 pass한 문제가 되었다.. ㅎㅎ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class MarblesRegroupingEasy {
  9 public:
 10
 11 int minMoves(vector <string> boxes)
 12 {
 13     int n, m;
 14     int i, j, k, l, temp;
 15     int cnt, min1;
 16     int color[101];
 17     char map[101][101];
 18     n = boxes.size();
 19     m = boxes[0].size();
 20     for (i = 0; i < n; i++) {
 21         strcpy(map[i], boxes[i].c_str());
 22     }
 23     min1 = 99999999;
 24     for (i = 0; i < n; i++) {
 25         cnt = 0;
 26         memset(color, 0, sizeof(color));
 27         for (j = 0; j < n; j++) {
 28             if (i == j)
 29                 continue;
 30             l = 0;
 31             for (k = 0; k < m; k++) {
 32                 if (map[j][k] != '0') {
 33                     temp = k;
 34                     l++;
 35                 }
 36             }
 37             if (l == 1) {
 38                 if (color[temp])
 39                     cnt++;
 40                 color[temp] = 1;
 41             }
 42             else if (l > 1) {
 43                 cnt++;
 44             }
 45         }
 46         if (cnt < min1)
 47             min1 = cnt;
 48     }
 49 printf("min1= %d\n\n", min1);
 50     return min1;
 51 }
 52
 53 };




[500] IntervalSubsets
input으로 여러개의 integer 구간이 들어온다.. 서로 겹치지않는 구간끼리 그룹화하여 생길수있는 그룹을 하나의 set으로 만들때, 나올수있는 set의 개수 구하기.. 단, 각 그룹에는 다른 구간을 더이상 추가할 수 없어야함.. 흠.. 문제해석이 어렵다.. ㅠ_ㅠ 자세한내용은 sample I/O를 보고 파악..;;

to be updated..




[950] StrangeArray



to be updated..


'Problem Solving > TopCoder logs' 카테고리의 다른 글

TopCoder TCO08 Qualification Round 3(3A)  (0) 2008.02.15
TopCoder TCO08 Qualification Round 1  (4) 2008.02.06
TopCoder SRM 390 Div1  (2) 2008.02.03
TopCoder SRM 389 Div1  (0) 2008.01.25
TopCoder SRM 388 Div1  (2) 2008.01.16
TopCoder SRM 386 Div 2  (4) 2008.01.06
TopCoder SRM 385 Div2 (완료)  (4) 2007.12.30
TopCoder SRM 384 Div2 (완료)  (2) 2007.12.20
TopCoder SRM 383 Div 2 (완료)  (0) 2007.12.14
TopCoder SRM382 DIV2  (2) 2007.12.13

to Top