백준 20058. 마법사 상어와 파이어스톰

tose33 2022. 6. 10. 14:50

20058번: 마법사 상어와 파이어스톰

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c

www.acmicpc.net

문제의 핵심이 되는 부분은 격자를 2^L x 2^L 크기로 나눠서 회전시키는 부분이었다.

처음에 코드를 짜기 쉽도록 새로운 (N+1 x N+1) 크기의 격자를 만들고 원본의 (2^L x 2^L) 좌표 부분만 회전시키고, 해당 부분을 원본에 반영시켰더니 시간 초과를 받았다.

한 (2^L x 2^L) 격자 부분을 회전시킬때마다 (N+1 x N+1) 크기의 격자를 만들고 연산했기 때문이었다.

그래서 (N+1 x N+1) 크기의 격자를 새로 만들지 않고 (2^L x 2^L) 크기의 격자를 새로 만들어서 원본 격자에서 해당 격자의 값을 가져와서 회전 시킨 후에, 다시 원본의 원래 자리에 반영시키는 방식으로 짰더니 통과했다.