백준 > 2164 카드2

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
 
void make(int i, int n, int arr[]);
void pop(int arr[], int n, int i);
 
int main() {
    int n;
    int i = 0;
    int num = 0;
 
    scanf("%d", &n);
 
    int* arr = (int*)malloc(sizeof(int) * (n / 2 + 1));
 
    if (n % 2 == 0) { //짝수인 경우
        n /= 2;
        make(i, n, arr);
    }
    else { //홀수인 경우
        arr[0] = n;
        n = n / 2 + 1;
        make(i + 1, n, arr);
    }
 
    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
            pop(arr, n, 0);
        }
        else {
            num = arr[n];
            n = n / 2 + 1;
            pop(arr, n, 1);
            arr[0] = num;
        }
    }
 
    printf("%d", arr[0]);
}
 
void pop(int arr[], int n, int i) {
    int j = 0;
 
    while (i < n) {
        arr[i] = arr[2 * j + 1];
        i++;
        j++;
    }
}
 
void make(int i, int n, int arr[]) { //배열에 원소 집어넣기
    int j = 1;
 
    while (i < n) {
        arr[i] = 2 * j;
        i++;
        j++;
    }
}

자료 구조인 큐를 쓰는 것이 정석인 문제다 (아마도)

하지만 이미 다른 방법으로 접근해버린 나머지.. 정석 큐를 쓰지 않고 문제를 풀겠다는 오기가 생겼다 

3일에 걸친 코드 수정 후에 해냈다ㅠㅠㅠ

 

1. N의 크기는 1이상 500000이하다 하지만 배열(큐)의 크기가 500000이여야 하나? 

예를 들어, 1 2 3 4 5 6인 카드가 있을 때 끝까지 카드를 한 번 거르면 2 4 6이 남는 것을 알 수 있다(짝수). 1 2 3 4 5인 카드가 있을 때 카드를 한 번 거르면 5 2 4가 남는 것을 알 수 있다(홀수).

따라서 카드 한 장을 제거하면 카드가 뒤로 한 장씩 보내지는 특성상 처음부터 카드를 한 번 걸러내면 최대 크기를 (절반+1)으로 줄일 수 있다.

 

2. 비슷한 방식으로 N이 1이 될 때까지 거르는 과정을 반복하면 된다.

N이 짝수이면 N/2, N이 홀수이면 N/2+1을 반복하며...

 

3. 처음에는 while문을 이용해 카드를 삭제하고, 한 장을 뒤로 보내는 과정을 반복했다. 그러니까 while문 안에 while문이 있던 셈인데...시간 초과가 날 수 밖에 없는 코드였다. 하지만 1, 2번의 방식을 적용하면 n이 절반씩 줄어드는거니까 n의 값이 500000이여도 대충 20번 안에는 다 끝난다. 그래서 이번 코드만은 시간 초과가 안날거라 예상했다.