C언어 179제] 2004년 한국정보올림피아드 지역본선 초등부 2번 줄 세우기

출처 : 반크_세계유산 경복궁

 

문제]

점심시간이 되면 반 학생 모두가 한 줄로 줄을 서서 급식을 탄다. 그런데 매일 같이 앞자리에 앉은 학생들이 앞에 줄을 서 먼저 점심을 먹고, 뒷자리에 앉은 학생들은 뒤에 줄을 서 늦게 점심을 먹게 된다. 어떻게 하면 이러한 상황을 바꾸어 볼 수 있을까 고민하던 중 선생님이 한 가지 방법을 내 놓았다. 그 방법은 다음과 같다.

학생들이 한 줄로 줄을 선 후, 첫 번째 학생부터 차례로 번호를 뽑는다. 첫 번째로 줄을 선 학생은 무조건 0번 번호를 받아 제일 앞에 줄을 선다. 두 번째로 줄을 선 학생은 0번 또는 1번 둘 중 하나의 번호를 뽑는다. 0번을 뽑으면 그 자리에 그대로 있고, 1번을 뽑으면 바로 앞의 학생 앞으로 가서 줄을 선다. 세 번째로 줄을 선 학생은 0, 1 또는 2 중 하나의 번호를 뽑는다. 그리고 뽑은 번호만큼 앞자리로 가서 줄을 선다. 마지막에 줄을 선 학생까지 이와 같은 방식으로 뽑은 번호만큼 앞으로 가서 줄을 서게 된다. 각자 뽑은 번호는 자신이 처음에 선 순서보다는 작은 수이다.

예를 들어 5명의 학생이 줄을 서고, 첫 번째로 줄을 선 학생부터 다섯 번째로 줄을 선 학생까지 차례로 0, 1, 1, 3, 2번의 번호를 뽑았다고 하자, 첫 번째 학생부터 다섯 번째 학생까지 1부터 5로 표시하면 학생들이 줄을 선 순서는 다음과 같이 된다.

첫 번째 학생이 번호를 뽑은 후 : 1
두 번째 학생이 번호를 뽑은 후 : 2 1
세 번째 학생이 번호를 뽑은 후 : 2 3 1
네 번째 학생이 번호를 뽑은 후 : 4 2 3 1
다섯 번째 학생이 번호를 뽑은 후 : 4 2 5 3 1
따라서 최종적으로 학생들이 줄을 선 순서는 4, 2, 5, 3, 1이 된다.

줄을 선 학생들이 차례로 뽑은 번호가 주어질 때 학생들이 최종적으로 줄을 선 순서를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에는 학생의 수가 주어지고 둘째 줄에는 줄을 선 차례대로 학생들이 뽑은 번호가 주어진다. 학생의 수가 100 이하이고, 학생들이 뽑는 번호는 0 또는 자연수이며 학생들이 뽑은 번호 사이에는 빈 칸이 하나씩 있다.

출력
학생들이 처음에 줄을 선 순서대로 1번부터 번호를 매길 때, 첫째 줄에 학생들이 최종적으로 줄을 선 순서를 그 번호로 출력한다. 학생 번호 사이에는 한 칸의 공백을 출력한다.

예제 입력 1 
5
0 1 1 3 2

예제 출력 1 
4 2 5 3 1

 

출처 : 백준_2605번

 

 

참고풀이]

#include <stdio.h>
#include <stdlib.h> //malloc(), free()

int main()
{
   //학생 수를 입력받는다.
   int N;
   int i,j;
   int x;
 
   scanf("%d",&N);
   if(N>0 && N<=100) //학생수는 100이하.
   {
      //학생들의 번호표를 받기 위하여 인원수의 동적배열을 선언한다.
      int *M=(int *)malloc(sizeof(int)*N);
      //학생들의 번호표에 대한 실제 학생들의 위치를 저장할 동적배열 선언한다. 
      int *Mi=(int *)malloc(sizeof(int)*N);

      //학생들의 번호표를 입력받는다.
      for(i=0;i<N;i++) 
      {
         scanf("%d",&M[i]);
         if(M[i]>=0 && M[i]<=i);
         else return 0;
      }

      //학생들의 번호표를 기준으로 실제 줄을 정한다.
      for(i=0;i<N;i++) //0 1 1 3 2
      {
         x=i-M[i]; //학생이 자신의 위치를 구한다. 
         for(j=i;j>x;j--) //원래 있던 학생들을 
            Mi[j]=Mi[j-1]; //한칸씩 뒤로 이동한다. 
         Mi[x]=i+1; //자신이 뽑은 위치에 저장한다. 
      }

      //학생들의 줄선 결과를 출력한다.
      for(i=0;i<N;i++) 
         printf("%d ",Mi[i]);

      //동적메모리를 해제한다.
      free(Mi);
      free(M);
   } 

   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 여름