2009 정보올림피아드 지역본선 문제 Review (2)-3

이번 솔루션은 다소 간단하다.
또한 내가 작년에 쓰다가 한 문제를 망치게 만든 바로 그 방법이기도 하다....
(당시 int 형 변수를 제곱한 만큼 신규 할당시켰더니 오버플로)

바뀐 줄은 강조해 놓았다.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, i, j;
    int higher = 0;
    int *tower = (int *)malloc(sizeof(int)*500001);
    FILE *fpi, *fpo;

    tower[0] = 100000000;
    fpi = fopen("INPUT.TXT", "r");
    fpo = fopen("OUTPUT.TXT", "w");
    fscanf(fpi, "%d", &n);

    for (i = 0; i < n; i++)
    {
        fscanf(fpi, "%d", tower + i);
        for (j = 0; j < i; j++)
        {
            if (tower[j] >= tower[i])
                higher = j + 1;
        }
        if (i != 0) fprintf(fpo, " ");
        fprintf(fpo, "%d", higher);
    }
    fclose(fpi);
    fclose(fpo);

    return 0;
}

.....;;

이 해법이 먹히는 까닭은 간단하다.

C 컴파일러는 함수, 블럭 맨 앞에 있는 변수들을 처음에 미리 설정해 놓는다.
이들은 운영체제 상에서 하나의 함수로 취급되어, 그 정보는 스택(stack)에 저장된다.
(시스템 콜/인터럽트 후에 적절한 작업 후 call, ret가 일어나기 때문이다.)

그러나 위와 같이 해 놓으면, *tower만 스택에 저장되고,
나머지는 힙(heap)에 저장된다. 힙은 포인터를 이용해 얼마든지[?] 확장할 수 있는 구조체이다.


고로 Stack Overflow가 일어나지 않는다.


지난번 글에 비해 이번 글은 상당히 늦었습니다. 시험 기간이라든지 등등...