[백준/C++] 10811번: 바구니

by

문제로 이동

(백준/C++) #10811: 바구니 뒤집기

#10811: 바구니를 뒤집다

'추천 관련글,

도현이의 바구니는 총 N개이며 각 바구니는 1부터 N까지 순차적으로 번호가 매겨져 있습니다. 바구니가 정렬되어 가장 왼쪽 바구니가 첫 번째 바구니이고 다음 바구니가 두 번째 바구니입니다.

www.acmicpc.net

설명

예제 사용

1 2 3 4 5

(입력 1 2) -> 2 1 3 4 5

(3 4 입력) -> 2 1 4 3 5

(1 4 입력) -> 3 4 1 2 5

(2 2 입력) -> 3 4 1 2 5

이렇게 돌아갑니다.

저는 3가지 방법으로 해결했습니다.

1. 두 개의 어레이 생성 및 해결

2. 알고리즘 헤더의 역함수로 풀기

반전(A, B); // 요소의 순서를 A에서 B로 역순으로 바꿉니다.

3. 수학적 추론을 통한 스왑 기능으로 풀기

2, 1, 4, 3, 5가 있을 때 1과 4가 입력되면

끝 값과 끝 값을 바꾸고 중간 값을 바꾸면 순서가 반대로 됩니다: (2, 3), (1, 4)

두 번만 변경했기 때문에 for(int i = 0; i < 4 - 1 / 2; i++),

스왑(1 + i, 4 – i)하면; 하면 끝값과 평균값이 서로 바뀝니다.

암호

1. 두 개의 어레이 생성 및 해결

#include <iostream>

using namespace std;

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

	int M, N;
	cin >> M >> N;

	int *arr = new int(M + 1); // 최종 배열
	int *arr2 = new int(M + 1); // 바꾼 수를 저장할 배열

	for (int i = 1; i <= M; i++) // 배열에 값 대입
	{
		arr(i) = i;
		arr2(i) = i;
	}

	for (int i = 0; i < N; i++)
	{
		int A, B;
		cin >> A >> B;
		int B_pos = B; // 뒤에서부터 역순으로 바꿔야하므로...
		for (int j = A; j <= B; j++)
		{
			// arr2 배열의 첫번째 배열에는 arr 배열의 마지막 값이 온다
			arr2(j) = arr(B_pos);
			B_pos--; // B_pos 감소
		}
		for (int i = 1; i <= M; i++) // 최종 배열에 갱신하는 작업
		{
			arr(i) = arr2(i);
		}
	}

	for (int i = 1; i <= M; i++) // 출력
	{
		cout << arr2(i) << " ";
	}
	cout << "\n";
	delete arr; // 동적 할당 해제
	return 0;
}

2. 알고리즘 헤더의 역함수로 풀기

#include <iostream>
#include <algorithm>

using namespace std;

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

	int M, N;
	cin >> M >> N;

	int *arr = new int(M + 1){ 0 }; // 동적 할당

	for (int i = 1; i <= M; i++) // 배열에 값 대입
	{
		arr(i) = i;
	}

	for (int i = 0; i < N; i++)
	{
		int A, B;
		cin >> A >> B;
		reverse(arr + A, arr + B + 1); // 1번 배열 ~ 4번 배열까지의 값을 역순으로 바꿈
	}

	for (int i = 1; i <= M; i++) // 출력
	{
		cout << arr(i) << " ";
	}
	cout << "\n";
	delete arr; // 동적 할당 해제
	return 0;
}

3. 수학적 추론을 통한 스왑 기능으로 풀기

#include <iostream>
#include <algorithm>

using namespace std;

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

	int M, N;
	cin >> M >> N;

	int *arr = new int(M + 1){ 0 };

	for (int i = 1; i <= M; i++)
	{
		arr(i) = i;
	}

	for (int i = 0; i < N; i++)
	{
		int A, B;
		cin >> A >> B;

		// 아래의 식을 세운 이유는 블로그 게시글에 설명
		for (int j = 0; j <= (B - A) / 2; j++)
		{
			swap(arr(A + j), arr(B - j));
		}
	}

	for (int i = 1; i <= M; i++)
	{
		cout << arr(i) << " ";
	}
	cout << "\n";
	delete arr; // 동적 할당 해제
	return 0;
}