[백준] 20187 종이접기 (골드 3)

별로 어렵지 않은 구현문제였는데 아이디어를 떠올리는 데 시간이 조금 걸렸습니다. 종이를 R, U, D, L 방향으로 접는데 k번 접고 난 이후에는 변의 길이가 1인 정사각형이 남아있어야 하므로 좌우 방향 접는 횟수와 상하 방향 접는 횟수가 동일하다는 조건이 문제에 주어져 있습니다. 문제를 푸는 키 아이디어는 결과적으로 반복된다는 것입니다. 2*2 정사각형의 상하좌우의 뚫린 구멍이 모두 결정되고 나면 그러한 정사각형이 반복되는 구조입니다. 그러한 구조는 잘 생각해본다면 가장 마지막으로 접은 좌우 방향, 그리고 상하 방향으로 결정됩니다. 그리고 그 정보를 통해 우리는 2*2 정사각형의 구멍을 채울 수 있습니다. 예를 들어, R L L D U L R D D U 으로 접는다면, 가장 마지막으로 접은 좌우방향은 ..

2023.05.13