본문 바로가기
CodingTest/백준

[c++] 백준 - 10812번: 바구니 순서 바꾸기

by Daybreak21 2023. 5. 10.

10812번: 바구니 순서 바꾸기 (acmicpc.net)

 

10812번: 바구니 순서 바꾸기

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2

www.acmicpc.net

#include <iostream>
#include <cstring>
using namespace std;

int main() {
	int N, M, begin, mid, end;
	cin >> N >> M;
	int* bsk = new int[N];
	for (int i = 0; i < N; i++) { bsk[i] = i + 1; }

	for (; M > 0; M--) {
		cin >> begin >> end >> mid;
		begin--; mid--; end--;

		int n = end - begin + 1;
		int* mv = new int[n];
		for (int i = 0; i < n; i++) mv[i] = bsk[begin + i]; 
		for (int i = 0; i < n; i++) bsk[((i + (end - mid + 1)) % n) + begin] = mv[i];
		delete[] mv;
	}
	for (int i = 0; i < N; i++) cout << bsk[i] << " ";
	delete[] bsk;

	return 0;
}


n = end-begin+1 : 바꿔야하는 횟수
end-mid+1 : 숫자가 밀리는 칸 수 

ex) 첫번째 회전

for (int i = 0; i < n; i++) mv[i] = bsk[begin + i];​
1 2 3 4 5 6 : 0  ~ 5 번째 까지의 배열의 값을 mv배열에 저장한다. 
for (int i = 0; i < n; i++) bsk[((i + (end - mid + 1)) % n) + begin] = mv[i];​

3 4 5 0 1 2 : 1 2 3 4 5 6 의 값으로 바뀌는  bsk배열의 인덱스

i + (end - mid + 1)  + begin : 3 4 5 6 7 8 
(i + (end - mid + 1) % n) + begin : 3 4 5 0 1 2 

(end - mid + 1) 를 더하여 값이 이동되는 만큼 인덱스를 옮겨주었다. 
n으로 수정해야 할 배열의 인덱스를 넘으면 시작점(begin)으로 넘어가도록 하였다.