CODEONWORT

Memory 본문

Season 1/Problem solving

Memory

codeonwort 2013.12.24 09:53

문제 출처 http://koistudy.net/?mid=prob_page&NO=390


금방 풀 것 같았는데 의외로 테스트를 통과하지 못하고 질질 끌었다. 먼저 [1 1]에서 시작해서 X 버튼이나 Y 버튼을 누르는 경우를 5~6단계까지 전부 그려보며 패턴을 찾아내기는 개뿔 하나도 못 찾았다.


방향을 바꿔서 [n 1] [n 2] [n 3] ... [n n-1]에서 [1 1]을 만드는 방법은 어떨까? 예를 들어 [n 1] <- [n-1 1] <- [n-2 1] <- ... <- [2 1] <- [1 1]처럼 둘 중 큰 수에서 작은 수를 빼서 [1 1]을 찾아가는 것이다. [1 1]이 안 되는 경우도 있는데 가령 [6 3]에서 시작하면 [6 3] <- [3 3] <- [0 3] 또는 [3 0]이 되는데 0은 나올 수 없으므로 [6 3]은 애초에 [1 1]에서 출발해서는 만들 수 없다. 그 외에 가능한 모든 경우에서 가장 연산 수가 적은 경우를 찾는다.


여담이지만 조금 생각해보면 [x y]에서 x와 y가 서로소가 아니면 [1 1]에서 시작해서 만들 수 없음을 증명할 수 있다. 이걸 이용해서 경우의 수를 줄일 수도 있겠지만 귀찮음


처음에는 구조체와 큐를 쓰는 뻘짓을 했다가 시간 초과라는 똥을 받았다. 게다가 [n 2]와 [n n-2]처럼 연산 순서가 단순히 X/Y가 뒤집히는 쌍은 하나만 고려했다가 사전순으로 가장 빠른 답을 찾는 것에 실패했다. 마지막에 invert 어쩌구 부분은 이것을 해결해보려는 뻘짓이고 실패했다.


#include <stdio.h>

#include <stdlib.h>


typedef struct pair {

  int x,y;

  char op;

  struct pair *link;

  struct pair *next;

} * Pair;


typedef struct queue {

  Pair first;

  int length;

} * Queue;


Pair makePair(int x, int y, Pair link, char op) {

  Pair p = (Pair)malloc(sizeof(struct pair));

  p->x = x;

  p->y = y;

  p->link = link;

  p->next = NULL;

  p->op = op;

  return p;

}


Queue makeQueue() {

  Queue q = (Queue)malloc(sizeof(struct queue));

  q->first = NULL;

  q->length = 0;

  return q;

}


void push(Queue q, Pair p) {

  Pair tail;

  if(q->length == 0){

    q->first = p;

  }else{

    tail = q->first;

    while(tail->next) tail = tail->next;

    tail->next = p;

  }

  q->length ++;

}


Pair pop(Queue q) {

  Pair p;

  if(q->length){

    p = q->first;

    q->first = q->first->next;

    q->length --;

    return p;

  }

  else return NULL;

}


void main() {

  int n,i,found=0,cnt=-1,invert;

  Queue q;

  Pair p;


  scanf("%d", &n);

  q = makeQueue();


  for(i=2/n; i<n; i++) push(q, makePair(n, i, NULL, 0));

  while(!found){

    n = q->length;

    while(n--){

      p = pop(q);

      if(p->x == 1 && p->y == 1){

        found = 1; break;

      }else if(p->x > p->y) push(q, makePair(p->x - p->y, p->y, p, 'X'));

      else if(p->x < p->y) push(q, makePair(p->x, p->y - p->x, p, 'Y'));

    }

    cnt++;

  }


  printf("%d\n", cnt);


  invert = p->op == 'Y' ? 1 : 0;

  while(p->link){

    if(p->link->link){

      if(p->op == 'X') putchar(invert ? 'Y' : 'X');

      else putchar(invert ? 'X' : 'Y');

    }else putchar('X');

    p = p->link;

  }

}


결론은 최소 연산 횟수는 제대로 구하나 사전 순으로 가장 빠른 답은 찾지 못한다는 것이다. 일단 시간 제한 초과를 해결해보고자 구조체와 큐를 지웠다.


#include <stdio.h>

#include <stdlib.h>


int count(int x, int y) {

  int c = 0;

  while(1){

    if(x > y) x -= y;

    else if(x < y) y -= x;

    else{ c=-1; break; }

    c++;

    if(x==1 && y==1) break;

  }

  return c;

}


void print(int x, int y, int step){

  char *seq;

  printf("%d\n", step);

  seq = (char*)malloc((step+1) * sizeof(char));

  seq[step] = 0;

  while(step){

    step--;

    if(x>y){ x-=y; seq[step] = 'X'; }

    else{ y-=x; seq[step] = 'Y'; }

  }

  puts(seq);

  free(seq);

}


void main() {

  int n,i, minstep,step,y=1;


  scanf("%d", &n);


  minstep = count(n, y);

  for(i=2; i<n/2; i++){

    step = count(n, i);

    if(step != -1 && step < minstep){

      minstep = step;

      y = i;

    }

  }

  print(n, y, minstep);

}


코드가 더 깔끔해지고 속도도 빨라졌다. 자료구조는 배웠다고 막 쓰는 게 아니다.


이제 연산 횟수가 최소인 여러 답 중 사전 순으로 가장 빠른 답을 찾아야 한다. 위에서는 연산 횟수가 최소가 되는 y를 찾아 그 경우만 답 문자열을 계산했는데, 이번에는 그냥 모든 경우에 답 문자열을 구하고, 루프를 돌리다 지금보다 더 적은 횟수를 구하면 답을 치환하고, 횟수가 같으면 답을 비교해서 사전 순으로 빠르면 치환한다.


#include <stdio.h>

#include <stdlib.h>

#include <string.h>


int count(int x, int y, char* seq) {

  int i,c = 0;

  while(1){

    if(x > y){ x -= y; seq[c] = 'X'; }

    else if(x < y){ y -= x; seq[c] = 'Y'; }

    else{ c=-1; break; }

    c++;

    if(x==1 && y==1) break;

  }

  seq[c] = 0;

  return c;

}


int lt(char *a, char *b, int n) {

  int i;

  for(i=n-1; i>=0; i--){

    if(a[i] < b[i]) return 1;

    else if(a[i] > b[i]) return 0;

  }

  return 0;

}


void main() {

  int n,i,minstep,step;

  char *seq, *minseq;


  scanf("%d", &n);

  seq = (char*)malloc(n * sizeof(char));

  minseq = (char*)malloc(n * sizeof(char));


  minstep = count(n, 1, minseq);

  for(i=2; i<n; i++){

    step = count(n, i, seq);

    if(step != -1){

      if(step < minstep){

        minstep = step;

        strcpy(minseq, seq);

      }else if(step == minstep && lt(seq, minseq, step)){

        strcpy(minseq, seq);

      }

    }

  }

  if(minstep != -1){

    printf("%d\n", minstep);

    for(i=minstep-1; i>=0; i--) putchar(minseq[i]);

  }else printf("%d", 0);

}


문제는 풀었지만 아쉬움이 많이 남는다. 규칙이나 공식을 찾아서 답을 빠르게 구하는 것도 아니고 노가다라 코드가 길고 느리다. 1등인 사람은 15ms만에 테스트가 끝났지만 내 코드는 112ms나 걸린다. 이 문제는 나중에 더 효율적인 알고리즘을 찾아봐야겠다.

0 Comments
댓글쓰기 폼