어제 밤 12시에 열린 매치..~
야비군훈련 가서 하루죙일 추위에 떨다가 돌아와서 머리 띵한 상태에서 참여했다..~
250점은 쉬운문제인데도 불구하고 뭔가 함정이 있는지.. 다들 줄줄이 fail했다..
그래도 나는 pass할 줄 알았는데 나도 챌 당했다.. 알고보니 어처구니없는 코딩 실수를.. ㅠ_ㅠ 아 열받아..
요즘들어 컨디션이 안좋은건지.. 아니면 벌써 노화가 오는건지 코딩이 자꾸 꼬인다.. 쩝..
결국 0점으로 마감.. ㅠ_ㅠ




[250] TheSwap

more..

n이 주어지고 임의의 두개 digit을 swap할 수 있다.. 단 swap 결과로 인해 leading zero가 생기면 안된다.. 이러한 swap 을 딱 k번 할 때 만들 수 있는 가장 큰 수 구하기..

문제 보자마자 대략 큰 수가 앞으로 나오도록 swap을 해보려고 했는데.. 어떤 방법으로 해도 최적이 되는 방법을 찾는게 쉽지 않았다.. 그래서 그냥 backtracking을 시도..~ 삽질끝에 submit했는데.. 시간복잡도를 대충 계산해보니 무려 O((6*5)^10)  -_-;; 기겁을 하고 다시 memorization해서 같은 상태를 두번이상 계산하지 않도록 고쳐서 resubmit..~ 가능한 모든 상태공간은 N*K 이다..

챌 당한 이유는 단순한 코딩 실수였는데.. cnt+1 을 그냥 cnt라고 적어놨었다.. 젠장.. ㅠ_ㅠ
이거 찾은놈 대단하네..

어쨋든 backtracking의 진수를 보여준 좋은 문제..~

  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 max1, K;
 10 char check[1000001][11];
 11
 12 void dfs(int n, int cnt)
 13 {
 14     int len, i, j, p;
 15     char buf[100], buf2[100];
 16     if (cnt == K) {
 17         max1 = max(max1, n);
 18         return ;
 19     }
 20     sprintf(buf, "%d", n);
 21     len = strlen(buf);
 22     strcpy(buf2, buf);
 23     for (i = 0; i < len; i++) {
 24         for (j = i+1; j < len; j++) {
 25             if (i == 0 && buf[j] == '0')
 26                 continue;
 27             strcpy(buf2, buf);
 28             buf2[i] = buf[j];
 29             buf2[j] = buf[i];
 30             p = atoi(buf2);
 31             if (!check[p][cnt+1]) {
 32                 check[p][cnt+1] = 1;
 33                 dfs(atoi(buf2), cnt+1);
 34             }
 35         }
 36     }
 37 }
 38
 39 class TheSwap {
 40 public:
 41
 42 int findMax(int n, int k)
 43 {
 44     K = k;
 45     max1 = -1;
 46     memset(check, 0, sizeof(check));
 47     check[n][0] = 1;
 48     dfs(n, 0);
 49 printf("max1 = %d\n", max1);
 50     return max1;
 51 }
 52
 53 };



[500] TheInteger

more..

n과 k가 주어질 때 n보다 크거나 같으면서 k 종류개의 digit으로만 이루어진 가장 작은 수 구하기..


to be updated..



[1000] TheSum

more..



to be updated..




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

[SRM 444] 개인 역대 최고 등급 경신..~  (0) 2009.07.09
TopCoder SRM 442 Div 1  (11) 2009.06.14
[SRM 441] 탑코더 아레나.. 중국 뉴비들에게 DDOS공격 받고 사망..  (0) 2009.05.28
TopCoder SRM 440 Div 1 - 드디어 Yellow 등극..  (0) 2009.05.14
말많고 탈많았던 SRM 438  (4) 2009.04.20
TopCoder SRM 437 Div 1  (0) 2009.03.25
TCO09 Round 1  (0) 2009.03.08
TCO09 Qual 3 (완료)  (0) 2009.03.05
TCO09 Qual 2  (0) 2009.03.01
TCO09 Qual 1  (0) 2009.02.25
TopCoder SRM 434 Div 1  (0) 2009.02.10

Leave a Comment


to Top