백준 Gold 3 종이접기

종이접기 (백준 Gold 3)

https://www.acmicpc.net/problem/20187

특정한 수 k가 주어지고,
종이를 접는 방법이 2k개 주어진다

• 위와 같은 종이 접는 방법이 ‘대문자 알파벳’으로 주어진다
  

• 그리고 다음처럼 1x1 인 정사각형이 되었을때 특정한 방향에
  구멍을 뚫었을 수 있다
  

• 최종적으로 ‘종이를 다 폈을 때’ 보이는 종이들의 ‘구멍 뚤린 방향’을 출력하는 문제
  

  • 종이를 피는 순은 ‘접는 방법’의 역순
    

풀이 방법

일단 문제를 자세히 보자면
‘굳이 접는 것’ 부터 시작할 필요는 없어보인다

• 결국 1x1 에서 구멍을 뚫어야 하므로
  1x1 배열에서 ‘접는 방향’의 역순으로 늘어나는 방식을 고려하였다
  

• 위와 같이 ‘역’으로 ‘늘어나는’ 쪽으로 계산하되
  ‘방향’은 대칭이 되는 쪽의 숫자를 대입해주면 풀 수 있는 문제
  
  • 그 경우, ‘해당 시점’의 인덱스를 잘 계산해야 하기에
    절반의 h와 w를 기반으로 ‘현재 유지’될 인덱스와
    뒤집힐 인덱스를 함수를 통해 구하도록 설정함
    

제출 코드

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

int getIdx(char c, int now)
{
	int ret = -1;
	switch (c)
	{
	case 'D':
	case 'U':
	{
		switch (now)
		{
		case 0:
			ret = 2;
			break;
		case 1:
			ret = 3;
			break;
		case 2:
			ret = 0;
			break;
		case 3:
			ret = 1;
			break;
		}
	}
	break;
	case 'R':
	case 'L':
	{
		switch (now)
		{
		case 0:
			ret = 1;
			break;
		case 1:
			ret = 0;
			break;
		case 2:
			ret = 3;
			break;
		case 3:
			ret = 2;
			break;
		}
	}
	break;
	}

	return ret;
}

vector<vector<int>> Pages(char c,vector<vector<int>>& input)
{
	int h = input.size();
	int w = input[0].size();

	switch (c)
	{
	case 'D':
	case 'U':
	{
		h *= 2;
	}
	break;
	case 'R':
	case 'L':
	{
		w *= 2;
	}
	break;
	}

	vector<vector<int>> ret(h, vector<int>(w));

	switch (c)
	{
	case 'D':
	{
		int halfh = h / 2;
		// 반대로 위를 향해 올린다
		// 따라서 halfh ~ h 까지는 기존 input 값을 유지시킴
		// 그리고 0~halfg 까지는 대비되게 짜야 함

		for (int i = 0; i < halfh; i++)
		{
			for (int j = 0; j < w; j++)
			{
				// 이쪽은 뒤집히므로, y축 역순이여야 함
				ret[i][j] = getIdx(c, input[halfh - i - 1][j]);
			}
		}

		for (int i = halfh; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				// 이쪽은 정순이여야 함
				ret[i][j] = input[i - halfh][j];
			}
		}
	}
	break;
	case 'U':
	{
		int halfh = h / 2;
		// 반대로 아래로 내림
		// 따라서 0~ halfh 까지는 정순
		// halfh ~ h 까지 역순

		for (int i = 0; i < halfh; i++)
		{
			for (int j = 0; j < w; j++)
			{
				ret[i][j] = input[i][j];
			}
		}

		for (int i = halfh; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				ret[i][j] = getIdx(c,input[h - i - 1][j]);
			}
		}
	}
	break;
	case 'R':
	{
		int halfw = w / 2;
		// 반대로 왼쪽으로 확장
		// 0~halfw 까지 역순
		// halfw~w 까지 정순

		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < halfw; j++)
			{
				ret[i][j] = getIdx(c, input[i][halfw - j - 1]);
			}
		}

		for (int i = 0; i < h; i++)
		{
			for (int j = halfw; j < w; j++)
			{
				ret[i][j] = input[i][j - halfw];
			}
		}

	}
	break;
	case 'L':
	{
		int halfw = w / 2;

		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < halfw; j++)
			{
				ret[i][j] = input[i][j];
			}
		}

		for (int i = 0; i < h; i++)
		{
			for (int j = halfw; j < w; j++)
			{
				ret[i][j] = getIdx(c, input[i][w - j - 1]);
			}
		}
	}
	break;
	}

	return ret;
}

int main()
{
	int k;
	cin >> k;

	stack<char> os;
	for (int i = 0; i < k * 2; i++)
	{
		char c;
		cin >> c;
		os.push(c);
	}

	vector<vector<int>> ret(1, vector<int>(1));

	cin >> ret[0][0];

	for (int i = 0; i < k * 2; i++)
	{
		ret = Pages(os.top(), ret);
		os.pop();
	}

	int h = ret.size();
	int w = ret[0].size();

	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			cout << ret[i][j] << ' ';
		}
		cout << '\n';
	}

	return 0;
}

결과

• 그렇게까지 어려운 문제는 아니었으나
  구현 문제는 역시 문제 접근 방식과 그것을 어떻게 코드로 옮기는지를
  묻기에 시간을 많이 쓰는 것 같다…