[백준/BOJ] 10811번 바구니 뒤집기 (C/C++)

백준 온라인 저지(BOJ) 10811번 바구니 뒤집기
https://www.acmicpc.net/problem/10811

10811번: 바구니 뒤집기

* 사용언어 : C언어, C++

 

1. 문제

1번부터 N번까지 번호가 적힌 바구니가 순서대로 놓여있음
i번부터 j번까지 바구니의 순서를 M번 뒤집음
M번 뒤집은 후 바구니의 순서를 출력

 

2. 풀이

10813 공 바꾸기 문제의 응용 문제라고 보면 될 것 같습니다.
이 문제는 바구니만 고려하면 되기 때문에 상대적으로 쉬운 문제 같지만,
구현에 있어서는 이번 문제가 약간 더 어려운 것 같습니다.

(10813번 풀이는 아래 링크를 참고하시면 됩니다)
https://rightbellboy.tistory.com/151

[백준/BOJ] 10813번 공 바꾸기 (C/C++)

바구니를 뒤집는 절차를 어떻게 수행하냐에 따라서 2가지 방법으로 구현해볼 수 있습니다.

첫 번째 방법은 실제로 바구니를 교환하듯이 i번과 j번을 바꾸고, i는 +1, j는 -1 하면서 반복하는 방식입니다.
두 번째 방법은 tmp 배열을 선언해서 해당 배열에 매 회마다 i 부터 j 까지 역순으로 기록을 해두고,
이를 다시 원래 배열 arr 에 덮어쓰는 방식입니다.

 

2가지 소스 코드는 아래에 첨부해두었습니다. (메모리 및 시간은 동일)
아래 코드 참고하신 후 원하는 방식으로 구현해보시면 될 것 같습니다.

 

3. 코드

1) 직접 교환하는 방식

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <cstdio>

const int LM = 101;
int arr[LM];

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n, m, k;
	scanf("%d %d", &n, &m);

	for (k = 1; k <= n; ++k) arr[k] = k;
	
	int i, j, tmp;
	while (m--) {
		scanf("%d %d", &i, &j);
		while (i < j) {
			tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
			++i, --j;
		}
	}

	for (k = 1; k <= n; ++k) printf("%d ", arr[k]);
	return 0;
}

2) temp 배열 기록 방식

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <cstdio>

const int LM = 101;
int arr[LM], tmp[LM];

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n, m, k;
	scanf("%d %d", &n, &m);

	for (k = 1; k <= n; ++k) arr[k] = k;
	
	int i, j;
	while (m--) {
		scanf("%d %d", &i, &j);
		for (k = i; k <= j; ++k) tmp[k] = arr[j - k + i];
		for (k = i; k <= j; ++k) arr[k] = tmp[k];
	}

	for (k = 1; k <= n; ++k) printf("%d ", arr[k]);
	return 0;
}