[백준 2605] 줄 세우기 (C#, C++) - soo:bak

문제 링크

2605번 - 줄 세우기

설명

학생들이 뽑은 번호에 따라 최종적으로 줄을 서는 순서를 구성하는 문제입니다.

각 학생은 줄을 서는 자신의 차례에 0 이상 i 이하의 수 중 하나를 뽑습니다. 이 수는 자신이 앞사람 몇 명을 넘어 앞쪽으로 이동할지를 의미하며, 이 규칙을 처음부터 끝까지 차례로 적용했을 때의 최종 줄 선 순서를 출력합니다.

접근법

• 처음 줄에 선 학생부터 번호를 뽑고, 해당 값만큼 앞으로 이동합니다.
• 학생 번호는 1번부터 시작하며, 자신보다 앞의 학생들을 한 칸씩 뒤로 밀어낸 후 자신이 들어갑니다.
• i번째 학생이 k를 뽑았으면, 현재 위치에서 k칸 앞으로 이동시켜 해당 자리에 삽입합니다.

이 작업을 모든 학생에 대해 반복하면 최종 줄 서기 순서를 구할 수 있습니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    int n = int.Parse(Console.ReadLine());
    var draw = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    int[] order = new int[n];

    for (int i = 0; i < n; i++) {
      int k = draw[i];
      for (int j = i; j > i - k; j--)
        order[j] = order[j - 1];
      order[i - k] = i + 1;
    }

    Console.WriteLine(string.Join(" ", order));
  }
}

C++

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi stu(n);
  for (int i = 0; i < n; i++) {
    int draw; cin >> draw;
    for (int j = i; j > i - draw; j--)
      stu[j] = stu[j - 1];
    stu[i - draw] = i + 1;
  }

  for (int i = 0; i < n; i++)
    cout << stu[i] << (i < n - 1 ? " " : "\n");

  return 0;
}