Goal

Inversion Sequence를 Original Sequence로 변환하는 프로그램을 c언어로 구현 한다.

문제

1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 inversion sequence라고 한다.

예를들어 다음과 같은 수열의 경우
4 8 6 2 5 1 3 7
1앞에 놓인 1보다 큰 수는 4,8,6,2,5 이렇게 5개이고,
2앞에 놓인 2보다 큰 수는 4,8,6 이렇게 3개 이다.
따라서 4 8 6 2 5 1 3 7 의 inversion sequence 는 5 3 4 0 2 1 1 0 이 된다.

n과 1부터 n까지의 수를 사용하여 이루어진 수열의 Inversion sequence가 주어졌을 때, 원래의 수열을 출력하는 프로그램을 작성

풀이

Inversion Sequence가 입력으로 들어왔을때, 원래의 수열을 찾아내는 프로그램을 작성해야하는 문제 입니다.

코드

#include <stdio.h>

int main() {
    int n,i,j,position;
    scanf("%d",&n);
    int in[n+1],on[n+1];
    for(i = 1; i <=n; i++) scanf("%d",&in[i]);
    for(i = n; i >= 1; i--) {
        position = i;
        for(j = 1; j <= in[i]; j++) {
            on[position] = on[position+1];
            position++;
        }
        on[position] = i;
    }
    for(i = 1; i <= n; i++) printf("%d ",on[i]);

    return 0;

}