[C++] 백준 2605번 - 줄 세우기(!!!!!!!!!!)

문제

점심시간이 되면 반 학생 모두가 한 줄로 줄을 서서 급식을 탄다. 그런데 매일 같이 앞자리에 앉은 학생들이 앞에 줄을 서 먼저 점심을 먹고, 뒷자리에 앉은 학생들은 뒤에 줄을 서 늦게 점심을 먹게 된다. 어떻게 하면 이러한 상황을 바꾸어 볼 수 있을까 고민하던 중 선생님이 한 가지 방법을 내 놓았다. 그 방법은 다음과 같다.
학생들이 한 줄로 줄을 선 후, 첫 번째 학생부터 차례로 번호를 뽑는다. 첫 번째로 줄을 선 학생은 무조건 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번부터 번호를 매길 때, 첫째 줄에 학생들이 최종적으로 줄을 선 순서를 그 번호로 출력한다. 학생 번호 사이에는 한 칸의 공백을 출력한다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
using namespace std;

int main() {

    int n;
    scanf("%d", &n);
    vector <int> student;

    for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);
        student.insert(student.begin() + i - num, i + 1);
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", student[i]);
    }
    return 0;
}

리뷰

아 이거 규칙을 찾아내는게 너무 어려웠다... 처음엔 중첩반복문을 썼다가...지웠다가...무한 반복... 

결론은 내 머리로는 생각이 안나서 도움을 참조했따..ㅎ 담에 다시 풀어봐야겠다. 까먹을때즈음..

규칙을 찾으면 생각보다 쉬운문제였던것 같다 난 못찾앗지만 ㅋ

insert함수를 사용해서 푸는데 insert(삽입하고자 하는 위치를 가리키는 반복자, 삽입하고자 하는 값) 이렇게 쓴다. insert함수를 써서 반복문을 계산하면

i=0 insert(0,1) -> 0번째에 숫자1이 들어가야함  [1]

i=1 insert(0,2) -> 0번째에 숫자2가 들어가야함 [2,1]

i=2 insert(1,3) -> 1번째에 숫자3이 들어가야함 [2,3,1]

i=3 insert(0,4) -> 0번째에 숫자4가 들어가야함 [4,2,3,1]

i=4 insert(2,5) -> 2번째에 숫자5가 들어가야함 [4,2,5,3,1]

결국 이렇게 된다. 여기서 규칙을 찾아서 일반화하면

student.insert(student.begin() + i - num, i + 1);

이렇게 작성할 수 있따..

 

담에 꼭 다시 풀어바야지 흑흑 ㅜ

출처 

2605번: 줄 세우기 (acmicpc.net)

2605번: 줄 세우기