Graphics Programming
Memory 본문
문제 출처 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나 걸린다. 이 문제는 나중에 더 효율적인 알고리즘을 찾아봐야겠다.
