백준 22858. 원상 복구 (small)

백준 2024-08-12 오늘의 문제 중 첫 단계

22858. 원상 복구 (small)

1. 간단 설명

문제가 상당이 이해하기 어렵다

문제 설명에서는 D와 P를 이용해 S를 구하는 방법을 설명해주고,

이를 응용하여 D와 S를 이용하여 P를 구하는 법을 묻고있다

2. 예시

예제 1

D = 4 3 1 2 5

P = 1 4 5 3 2

일 때,

P를 D를 이용해 셔플을 진행하면

i = 1 : P의 D_1번째(4) 카드를 1번에 배치 => S[1] = 3
i = 2 : P의 D_2번째(3) 카드를 2번에 배치 => S[2] = 5
i = 3 : P의 D_3번째(1) 카드를 3번에 배치 => S[3] = 1
i = 4 : P의 D_4번째(2) 카드를 4번에 배치 => S[4] = 4
i = 5 : P의 D_5번째(5) 카드를 5번에 배치 => S[5] = 2

이런식으로 진행이 되는 것을 알 수 있다

D와 S를 이용하여 P를 구하기 전에 예제 하나만 더보고 가겠다

예제 2

P가 숫자라서 햇갈린다면, P를 알파벳으로 두고 생각해본다

D = 4 3 1 2 5
P = A B C D E

일 때,

마찬가지로 P를 D를 이용해 셔플을 진행하면

i = 1 : P의 D_1(4)번째 카드를 1번째에 배치 => S[1] = D
i = 2 : P의 D_2(3)번째 카드를 2번째에 배치 => S[2] = C
i = 3 : P의 D_3(1)번째 카드를 3번째에 배치 => S[3] = A
i = 4 : P의 D_4(2)번째 카드를 4번째에 배치 => S[4] = B
i = 5 : P의 D_5(5)번째 카드를 5번째에 배치 => S[5] = E

S = [D C A B E] 가 된다.

이를 통해 S[N] = P[D[N]] 라는 식을 구할 수 있다.

이제 문제가 요구한 대로 S와 D가 주어졌을 때, P를 구한다면

S[1] = D이다. 이는 P의 D_1(4)번째 카드를 1번째 배치하여 얻은 결과다. 그러므로 P[4] = D이다
S[2] = C이다. 이는 P의 D_2(3)번째 카드를 2번째 배치하여 얻은 결과다. 그러므로 P[3] = C이다
S[3] = A이다. 이는 P의 D_3(1)번째 카드를 3번째 배치하여 얻은 결과다. 그러므로 P[1] = A이다
S[4] = B이다. 이는 P의 D_4(2)번째 카드를 4번째 배치하여 얻은 결과다. 그러므로 P[2] = B이다
S[5] = E이다. 이는 P의 D_5(5)번째 카드를 5번째 배치하여 얻은 결과다. 그러므로 P[5] = E이다

이런식으로 구할 수 있다

P[ D[N] ] = S[N]을 통해 P를 역으로 얻을 수 있다

for(int i=0; i<N; i++){
	P[D[i] - 1] = S[i]; // 1 해주는 이유는 index 때문 
}

3. 알고리즘

1. N과 K를 입력받는다
2. S와 D를 입력받는다
3. K번 셔플의 역함수를 수행하여 D를 구한다
4. D를 출력한다

4. 소스코드

#include <iostream>
#include <memory.h>

using namespace std;

int N, K;
int D[10001];
int P[1000001], S[1000001];

// D 셔플의 역함수
// 
void Shuffle() {
	for (int i = 0; i < N; i++) {
		P[D[i] - 1] = S[i]; // -1 해주는 이유는 index 때문!
	}
	memcpy(S, P, sizeof(S)); // 얻은 P를 S에 저장한다
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	// 입력받기
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> S[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> D[i];
	}
	
	// K 번 셔플
	for (int i = 0; i < K; i++) {
		Shuffle();
	}

	// 출력
	for (int i = 0; i < N; i++) {
		cout << S[i] << " ";
	}
	cout << endl;
}

아이디어를 떠올리는게 어려웠던 문제

S[i] = P[D[i]] 를 통해서 역함수를 직접 구하려 했으나 구현이 어려워서 실패했다

그냥 이를 반복문에 넣어서 컴퓨터가 직접 구하도록 하는 방법을 배웠다