BOJ 1891 사분면

하나의 좌표평면은 네 개의 사분면으로 나눠지는데, 각 사분면을 또 네 개의 사분면으로 나누고, 또 그 각 사분면을 네 개의 사분면으로 나눌 수 있고... 이렇게 나눌 수 있는데,
그렇게 나눈 사분면에 번호를 붙일 것이다. 예를 들어 3번 사분면을 네 개의 사분면으로 나눠서 3번 사분면의 2번 사분면을 32 사분면으로 부르고, 3번 사분면의 2번 사분면으로 또 네개의 사분면으로 나누면 321 이라고 번호 붙일 수 있겠다. 문제에서 요구하는 것은 어떤 사분면의 번호가 주어지고 그 사분면에서 x축 방향으로 몇 칸, y축 방향으로 몇 칸 이동할지가 주어질 때, 이동한 후의 사분면 번호를 구하라는 것이다.

백준님의 명강의를 듣고 풀어보려고 한다.
문제의 풀이는 크게 2부분으로 나눌 수 있다.

1. 사분면 조각 위치 -> 좌표로 변환
2. 좌표로 주어진 수만큼 이동 후 좌표 -> 사분면 조각 위치로 변환

1. 주어진 사분면 조각 위치를 좌표(행, 열)로 변환하는 것부터 해보자.
일단, 행과 열은 0부터 시작하는 걸로 한다. 그리고 주어진 사분면 조각 위치의 길이(d)에 따라 행, 열의 길이가 결정된다. 길이는 2의 d제곱이 될 것이다.(d가 하나 늘어날 때마다 행, 열을 2등분하므로...)
사분면 조각 번호를 앞에서부터 보면서 변환하는데, 다음 번호로 넘어갈 때마다 행, 열이 분할되므로 범위가 달라진다. 하지만 구하는 방식은 일정하기 때문에 재귀를 이용한다.
 재귀 함수 내에서는, 주어진 범위와 조각 번호 한 자리를 이용한다. 주어진 범위(s~e)를 2등분 해서 행과 열을 각각 2등분할 수 있다..( s, (s+e)/2 ), ( (s+e)/2 + 1, e ) 그럼 자연스레 평면이 4등분 되는데 조각 번호 한 자리가
1이면 행은 s, (s+e)/2        열은 (s+e)/2 + 1, e
2이면 행은 s, (s+e)/2         열은 s, (s+e)/2
3이면 행은 (s+e)/2 + 1, e     열은 s, (s+e)/2
4이면 행은 (s+e)/2 + 1, e      열은 (s+e)/2 + 1, e 
이렇게 다음 조각 번호 한 자리와 함께 재귀함수를 호출하면서 범위를 좁혀 나가다가 마지막 조각 번호 한 자리에서 행 열 좌표를 구할 수 있을 것이다.

2. 좌표를 주어진 수만큼 이동하는 것은 쉽다. 그리고 그 좌표를 사분면 조각 번호로 변환하는 것을 해보자.
이 과정도 위의 1번 과정과 비슷할 것이다.
주어진 범위(s~e)를 2등분 해서 좌표의 행 번호와 열 번호가 어디에 속하냐에 따라 사분면 조각 번호 한 자리를 구하고,  그 범위와 좌표를 가지고 재귀함수를 호출하면서 범위를 좁혀 나가면 최종 사분면 조각 번호 한 자리까지 구할 수 있을 것이다.

이제 정리한 대로 구현 들어갑니다.
구현 중 알게 된것... 일단 꽤 복잡하다는 것 좀 헷갈린다.
그리고 좌표의 범위를 설정하려고 (예를 들어 d가 3이면 0부터 7이니 1<<3 - 1 = 7이 되겠지 했는데...) 1<<d-1을 했는데 d-1이 먼저 계산되고 <<가 계산되었다. (1<<d)-1을 해줘야 원하는 대로 되었다..
그리고 좌표 이동을 처리할 때, 난 행 열을 기준으로 해서 행은 위에서부터 아래로, 열은 왼쪽에서부터 오른쪽으로 0부터 커지는 식이었는데, 주어진 값대로 이동할 때 방향 잘 고려해서 (무조건 더하거나 빼지만 말고) 처리해줘야 한다!
그리고...d=50이고, x, y의 범위는 최대 2의 50제곱이므로.. long long을 써야한다는 것도...!
그리고 하나 더...
1<<d를 이용해서 long long범위의 수를 만들 수 있지만 주의할 점...
1LL이어야 한다는 점!!! 1LL<<d를 해줘야 한다!

AC를 받았다. 음 근데 다른 고수 분들의 코드를 보니 매우 짧다. 나랑은 비교도 안되게 짧고, 깔끔하다. 근데 이해는 아직 못했다. 한 번 이해해 해보려고 한다....-> 나중에 시간 되면 해봐야겠다. 풀어야 할 문제가 많다...


백준님 설명 메모

길이의 제한 50
잘 보면 반복된다. 재귀적으로 반복된다.
그리고 4개중에 하나를 찾고 또 그 하나를 4개로 나눠 하나를 찾고, 나머지 다 버리고 또 거기서 하나만 찾고... 이런 형식일 때는 그냥 재귀함수를 써주면 된다. 재귀적이고 형태도 똑같고.. 다른 부분은 크기만 다르다.(점점 작아진다)
341이 주어지면 처음부터 8칸씩으로 해서 그린다. ...

1. 사분면 조각이 주어지면 이것을 좌표로 바꾸는 것
ex) 341의 좌표는 6행 3열
2. 오른쪽으로 2칸 위로 한칸 -> 5행 5열 -> 몇인지 찾는다. ==> 좌표의 범위를 이용해서 나눠서 찾아가면 된다. 재귀로...

칸의 좌표를 r행 c열, 변의 길이를 size로 하면, 이 것을 4등분 하면 또 왼쪽 맨 위의 좌표는 4개... 


출처 : 백준님 강의, 강의 자료