악.. 결국 상승세를 이어가지못하고.. 또 망쳤다.. 이런.. 500점 문제는 처음에 잘 이해해서 다 풀어놓고.. 디버깅하다가 문제를 헷깔려서 이상하게 고치고말았다.. ㅠ_ㅠ 음.. 첫번째 문제는 방에서 3번째로 풀었는데.. 괜히 챌 시도해서 점수만 많이 날렸다.. 챌 성공률 26% 완전 극악의 성공률을 보이고있다.. 근데.. 나 코딩속도 조금 빨라진건가?

방 8등 전체 283등..

사용자 삽입 이미지


사용자 삽입 이미지


[250] LuckyTicketSubstring
문자열이 주어지고.. 그 문자열의 연속된 임의의 짝수 길이의 substring중에서 앞에 절반 digit sum이 뒤에 절반 digit sum과 같은 substring을 찾는것.. 그중에 가장 긴 길이를 찾는 문제..

brute force로 풀었다.. 모든 substring을 다 구하고.. 조건을 만족하는지 체크..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7 #define max(x, y) ((x) > (y) ? (x) : (y))
      8
      9 int check(char* str, int l)
     10 {
     11     int sum1, sum2;
     12     int i;
     13     sum1 = sum2 = 0;
     14     for (i = 0; i < l/2; i++)
     15         sum1 += str[i]-'0';
     16     for ( ; i < l; i++)
     17         sum2 += str[i] - '0';
     18     if (sum1 == sum2)
     19         return 1;
     20     return 0;
     21 }
     22
     23 class LuckyTicketSubstring {
     24 public:
     25
     26 int maxLength(string s)
     27 {
     28     char buf[100], sub[100];
     29     int len, max1;
     30     int i, j;
     31     strcpy(buf, s.c_str());
     32     len = strlen(buf);
     33     max1 = 0;
     34     for (i = 2; i <= len; i+=2) {
     35         for (j = 0; j+i-1 < len; j++) {
     36             strncpy(sub, &buf[j], i);
     37             sub[i] = 0;
     38             if (check(sub, i)) {
     39                 max1 = max(max1, i);
     40             }
     41         }
     42     }
     43     return max1;
     44 }
     45
     46 };



[500] LameKnight
LameKnight가 움직이는 규칙은 일반 knight와 같지만.. 무조건 오른쪽 방향으로 이동해야한다.. height * width 보드가 주어질때 (1, 1)에 있는 lame knight가 갈수있는 최대 cell의 개수 구하기.. 단 4번 이상의 move를 할 경우 무조건 4방향 move를 다 이용해야하고.. 그렇지 않다면 move하는 방향에 제약이 없다..

문제 해석이 좀 까다로웠던 문제.. 나중에 문제를 제대로 이해하고 풀었는데.. 디버깅중에 문제가 다시 헷깔리는바람에.. 챌 당한 문제.. ㅠ_ㅠ 쉬운문제였는데.. 아쉽다..

그냥 규칙을 꼼꼼하게 잘 따져보면서 if문을 남발하면 풀 수있다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 #define min(x, y) ((x) > (y) ? (y) : (x))
  8 #define max(x, y) ((x) > (y) ? (x) : (y))
  9
 10 class LameKnight {
 11 public:
 12
 13 int maxCells(int height, int width)
 14 {
 15     if (width == 1 || height == 1)
 16         return 1;
 17     if (width <= 2 && height <= 2)
 18         return 1;
 19     if (height <= 2)
 20         return min(4, (width+1)/2);
 21
 22     if (width < 7)
 23         return min(4, width);
 24     return width-2;
 25 }
 26
 27 };




[1000] CompilingDecksWithJokers
n 종류의 카드가 있고.. 각 종류별 카드의 개수와 조커의 개수가 주어진다.. 조커는 임의의 숫자를 대체할 수 있다.. {1, 2, 3, ..., n} 형식으로 각 종류별 카드가 하나씩 들어가게 해서 카드 묶음을 만들때 최대 몇개의 묶음을 만들 수 있는지 구하는 문제.. 각 묶음에는 최대 한개의 조커가 들어갈 수 있다..

이 문제는 가능한 묶음 수에 대해서 binary search해서 풀 수 있다.. 이러한 방법을 parametric search라고도 하는 것 같다.. ㅎㅎ

mid개의 묶음을 만들 수 있다고 가정할 때.. 묶음수보다 모자란 카드 종류에 대해서 그만큼 조커가 더 필요하다는 의미가 된다.. 이때 다음 두가지 사항을 반드시 만족해야 한다..

1) 필요한 조커 수 <= jokers
2) 필요한 조커 수 <= mid

첫번째 조건은 당연한 것이고.. 두번째 조건은 각 묶음에 들어갈 수 있는 조커 수는 최대 하나이기 때문이다..
두번째 조건을 생각해내는것이 조금 까다로웠다.. ;;;;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class CompilingDecksWithJokers {
  9 public:
 10
 11 int maxCompleteDecks(vector <int> cards, int jokers)
 12 {
 13     int n, i;
 14     long long left, right, mid;
 15     long long need, res;
 16     n = cards.size();
 17     left = right = 0;
 18     for (i = 0; i < n; i++) {
 19         if (right < cards[i] + jokers)
 20             right = cards[i] + jokers;
 21     }
 22     while (left <= right) {
 23         mid = (left + right) / 2;
 24         need = 0;
 25         for (i = 0; i < n; i++) {
 26             if (cards[i] < mid)
 27                 need += mid - cards[i];
 28         }
 29         if (need <= jokers && need <= mid) {
 30             res = mid;
 31             left = mid + 1;
 32         }
 33         else {
 34             right = mid - 1;
 35         }
 36     }
 37     return (int)res;
 38 }
 39
 40 };


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

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
TopCoder SRM381 DIV2 (완료)  (2) 2007.12.09
TopCoder SRM380 DIV2 (완료)  (0) 2007.12.08
TopCoder SRM 379 Div2 (완료)  (0) 2007.11.29
TopCoder SRM378 DIV2 (완료)  (0) 2007.11.21
TopCoder SRM375 DIV2 (Complete)  (6) 2007.11.11
TopCoder SRM374 DIV2  (3) 2007.11.07
TopCoder SRM 373 Div 2  (0) 2007.10.24

Leave a Comment


to Top