# [Silver II] 내 집 마련하기 [문제 링크](https://www.acmicpc.net/problem/30619) ## 문제 설명 <p>서강대학교에는 비어 있는 집이 $N$채 있다. 그래서 서강대학교는 $N$명의 사람들이 한 사람당 한 채의 집에 입주해 살 수 있도록 배정해 주려고 한다. 서강대학교에서는 입주한 사람들을 위해 특별한 혜택을 제공하는데, 바로 $x$번 집에 $y$번 사람이 입주해서 살게 되면 $xy$만큼의 세금을 감면해 준다는 것이다.</p> <p>사람들이 집에 배정된 상태는 $1$부터 $N$까지의 정수를 하나씩 원소로 가지는 수열 $A_1,A_2,\cdots,A_N$로 표현되는데, 이는 현재 $i$번 집에 $A_i$번 사람이 배정되어 있음을 의미한다. </p> <p>다음과 같은 쿼리를 해결하는 프로그램을 작성해 보자.</p> <ul> <li>$L$ $R$: 초기의 집 배정 상태에서, $L$번부터 $R$번까지의 사람들에게 이미 배정된 집들을 학교가 원하는 만큼 서로 교환해 재배정할 수 있을 때, 감면되는 세금의 합이 최대가 되도록 집에 사람들을 새롭게 배정하였을 때의 수열 $A$를 출력한다.</li> </ul> <p>모든 쿼리는 <strong>독립적</strong>이다. 즉, 쿼리가 실행된 직후 수열 $A$는 초기 상태로 복구된다.</p> ## 입력 <p>첫째 줄에 수열의 길이를 나타내는 정수 $N$이 주어진다. $(1\leq N \leq 300)$</p> <p>둘째 줄에 정수로 이루어진 수열 $A_1,A_2,\cdots,A_N$이 공백으로 구분되어 주어진다. $(1\leq A_i \leq N)$</p> <p>셋째 줄에 쿼리의 개수를 나타내는 정수 $M$이 주어진다. $(1\leq M \leq 300)$</p> <p>넷째 줄부터 $M$개의 줄에 걸쳐 쿼리를 나타내는 두 정수 $L,R$이 공백으로 구분되어 주어진다. $(1\leq L \leq R \leq N)$</p> ## 출력 <p>쿼리마다 정답을 한 줄에 하나씩 출력한다. </p> <p>각 줄에는 쿼리가 끝난 후 수열 $A_1,A_2,\cdots,A_N$을 공백으로 구분하여 출력한다.</p> <p>가능한 답이 여러 가지라면, 아무거나 하나 출력한다.</p> ## 풀이 큰 사람이 뒤로 가는 것이 더 효율적이다. L, R이 사람 범위를 나타내는 것이니 A[i]를 반대로 저장해서 정렬하면 쉽게 구현 가능하다. ``` c++ #include<bits/stdc++.h> using namespace std; int pos[301], cur[301]; // pos[i] : i번 사람이 pos[i]번 위치에 있다. int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=1;i<=n;i++) { int a; cin >> a; pos[a]=i; } int m; cin >> m; while(m--) { memcpy(cur, pos, sizeof cur); int l, r; cin >> l >> r; sort(cur+l, cur+r+1); vector<int> res(301); for(int i=1;i<=n;i++) res[cur[i]]=i; for(int i=1;i<=n;i++) cout << res[i] << ' '; cout << '\n'; } } ```