출처
- https://www.swexpertacademy.com
난이도
- 하 – 중 – (상) – 최상 – 풀지못함
문제
- 7장의 카드가 순서대로 나열되어 있다. 그리고 각 순서(Turn)마다 카드를 교환하는 방법을 준다. 예를 들어 이번 순서에는 2번째 카드와 3번째 카드를 교환한다. 총 교환해야 하는 횟수가 주어질 때 최종 카드 순서를 찾는 문제이다.
- SW Expert Academy의 경우 문제 공개를 하면 안 된다고 되어있어서 상세히 문제를 설명하지 않았다. 상세한 내용은 위 사이트에서 확인하면된다.
후기
- 처음에는 문제가 어렵다는 생각을 하지 않았다. 하지만, 최대 교환해야 하는 횟수가 엄청나게 크다 보니 무작정 모든 방법을 다 계산할 수 없었다.
- 그래서 몇 시간을 고민하다가 분할 정복 알고리즘 방식을 이용하여 문제를 해결하였다. 예를 들어 3가지 교환 방법(패턴)을 주면, 3번 교환한 카드 순서를 가지고 6번째 카드 순서를 알 수 있다. 3번째 카드 순서의 번호가 바로 6번째 카드 순서의 Index를 의미한다. 만약 아래 그림처럼 0 2 3 4 1 5 6의 순서가 3번째 Turn 카드 순서라면, 6번째 카드 순서는 3번째 카드 순서의 Index에 저장된 값을 읽어오면 6번째 카드 순서가 완성된다. 이와 동일한 방법으로 6번째 카드 순서를 이용하면 12번째 카드 순서 또한 계산할 수 있다.
그림 1: 2배씩 증가하면서 카드 순서를 계산하는 방법
- 위 설명(그림)과 같이 2배씩 증가하면서 카드 순서를 찾게되면 아무리 큰 수도 금방 찾을 수있다. 2배씩 증가하다가 남은 수 만큼은 그냥 For Loop을 사용해서 문제를 해결하면 된다.
코드
- 분할 정복 알고리즘을 사용하여 문제를 해결함
- Github 주소: https://github.com/mkblog-cokr/algorithmCode
- 실행 시간: 1ms (제일 빠른 코드와 동일 수준)
//MK: 분할 정복 알고리즘을 사용하여 문제를 해결함
#include <stdio.h>
//MK: Visual Studio를 사용시 scanf 에러 제거함
#pragma warning(disable:4996)
#define MAXSIZE 21
#define INPUTSIZE 7
int inputList[INPUTSIZE];
int answer[INPUTSIZE];
int input[MAXSIZE][2];
int position[MAXSIZE][INPUTSIZE];
typedef unsigned long long ull;
ull numShuffle, totalShuffle;
//MK: 아래 moveTwice 연산 후 결과를 계산하는 부분
void combine() {
int tmp[INPUTSIZE];
for (int i = 0; i < INPUTSIZE; i++) {
tmp[i] = answer[i];
}
for (int i = 0; i < INPUTSIZE; i++) {
answer[i] = tmp[inputList[i]];
}
}
//MK: 현재 주어진 카드 순서를 2배수 만큼 더 교환했을때 결과를 계산하는 부분
void moveTwice() {
int tmp[INPUTSIZE];
for (int i = 0; i < INPUTSIZE; i++) {
tmp[i] = inputList[i];
}
for (int i = 0; i < INPUTSIZE; i++) {
inputList[i] = tmp[tmp[i]];
}
}
//MK: moveTwice로 연산을 완료 후 남은 교환 횟수 만큼 연산을 하는 부분
void moveByPtr(ull ptr) {
int tmp[INPUTSIZE];
for (int i = 0; i < INPUTSIZE; i++) {
tmp[i] = answer[i];
}
for (int i = 0; i < INPUTSIZE; i++) {
answer[i] = tmp[position[ptr][i]];
}
}
//MK: 결과 계산하는 부분
void printAnswer(int testcase) {
printf("#%d ", testcase);
for (int i = 0; i < INPUTSIZE; i++) {
printf("%d", answer[i]);
}
printf("\n");
}
int main() {
freopen("input.txt", "r", stdin);
int testCase;
scanf("%d", &testCase);
for (int m = 0; m < testCase; m++) {
for (int i = 0; i < INPUTSIZE; i++) {
position[0][i] = i;
answer[i] = i;
}
scanf("%lld %lld", &numShuffle, &totalShuffle);
for (int i = 1; i <= numShuffle; i++) {
for (int j = 0; j < INPUTSIZE; j++) {
position[i][j] = position[i - 1][j];
}
scanf("%d %d", &input[i][0], &input[i][1]);
input[i][0]--;
input[i][1]--;
int tmp = position[i][input[i][0]];
position[i][input[i][0]] = position[i][input[i][1]];
position[i][input[i][1]] = tmp;
}
//MK: 결과를 계산하는 부분
if (totalShuffle <= numShuffle) {
moveByPtr(totalShuffle);
}
else {
ull currentTurn = 0;
while (1) {
ull nextMax = totalShuffle - currentTurn;
if (nextMax <= numShuffle) {
moveByPtr(nextMax);
break;
}
for (int i = 0; i < INPUTSIZE; i++) {
inputList[i] = position[numShuffle][i];
}
ull nextTurn = numShuffle;
//MK: 현재의 카드 순서를 가지고 2배수 만큼 교환을 하였을때 결과를 계산하는 부분
while ((nextTurn * 2) < nextMax) {
moveTwice();
nextTurn *= 2;
}
combine();
currentTurn += nextTurn;
}
}
printAnswer(m + 1);
}
return 0;
}