[백준] 22858 - 원상 복구 (small)

1. 문제

22858번: 원상 복구 (small)

2. 개요

수가 적혀있는 N개의 카드가 있다.

1부터 N까지 수가 하나씩 존재하는 배열 D가 있다.

이때 Di는 P[Di] 값을 i 번째로 가지고 오는 것을 의미한다. 이러한 작업을 카드 섞기라고 부른다. 카드를 섞는 작업은 동시에 진행된다.

배열 D와 이를 이용해 K번 섞은 카드들의 정보 S가 주어졌을 때, 초기 카드의 배치를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

섞는 방법을 역으로 이용해 답을 구할 수 있다.

섞은 이후의 카드 정보를 after 섞기 전의 카드 정보를 before 라고 하자.

위의 설명대로라면, after[i] = before[Di]이므로 이를 역으로 진행한 before[Di] = after[i]을 이용할 수 있다.

restore 함수를 작성한다.

완성된 S부터 after로 시작하여 before를 새로 작성하면서 위 식을 그대로 이용한다.

카운트를 1씩 늘리면서 K에 도달하지 못했다면 만들어진 before을 after로 하여 재귀를 돌린다.

cnt가 K에 도달했다면 만들어진 before의 정보를 출력한다.

3-2. Python

 import sys

sys.setrecursionlimit(10000000)

N, K = map(int, sys.stdin.readline().split())

S = list(map(int, sys.stdin.readline().split()))

D = list(map(int, sys.stdin.readline().split()))

def restore(after, cnt = 0):
    before = [0 for i in range(N)]

    for i in range(N):
        before[D[i] - 1] = after[i]

    cnt += 1

    if cnt < K:
        restore(before, cnt)

    else:
        print(*before)

restore(S)

3-3. C#

namespace boj_22858
{
    internal class Program
    {
        static int N;
        static int K;
        static int[] S;
        static int[] D;
        static int[] result;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();

            N = int.Parse(input[0]);
            K = int.Parse(input[1]);

            S = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            D = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

            result = Restore(S);

            foreach (int num in result)
                sw.Write($"{num} ");

            sw.Close();
        }

        static int[] Restore (int[] after, int cnt = 0)
        {
            int[] before = new int[N];

            for (int i = 0; i < N; i++)
                before[D[i] - 1] = after[i];

            cnt++;

            if (cnt < K)
                before = Restore(before, cnt);

            return before;
        }
    }
}