[BOJ] 백준 1074 Z (Swift)

문제

풀이

문제에서 주어진 표를 2 * 2 형태가 될 때 까지 분할을 해주어야 한다.
n이 3이라면, 8 x 8 형태일 것이고, 4개로 분할을 하면 중간값이 4일 것이다.

즉 중간값은 $2^n % 2$로 볼 수 있다.

중간 값이 정해졌다면, 좌표가 어느 공간에 속했는지 확인해주자.

1. y값이 0 ~ mid 사이, x 값이 0 ~ mid 사이
2. y값이 0 ~ mid 사이, x 값이 mid ~ $2^n$ 사이
3. y값이 mid ~ $2^n$ 사이, x 값이 0 ~ mid 사이
4. y값이 mid ~ $2^n$ 사이, x 값이 mid ~ $2^n$ 사이

n이 1이 될 때 까지 n을 1씩 줄여 반복을 해주면 y,x 값이 0 ~ 1 사이에 있을 것이다.

구간을 찾으면서, 해당 구간의 시작점? 을 누적해서 더해주어야 한다.

n이 3이라고 가정했을 때,

• 2번 구간은 16
• 3번 구간은 32
• 4번 구간은 48

로 볼 수 있다.
이는 $2^n * 2^n$으로 볼 수 있다. 중간 값 * 중간 값으로 이해하면 된다.

재귀함수로 구현했을 때 코드는 다음과 같다.

소스코드

후기

코드가 넘 지저분해서 깔끔하게 쓰는 습관을 가져야겠다.
그리고 설명을 너무 못하겠다...