
#include <stdio.h>
int main(){
int a;
scanf("%d", &a);
int n = 2;
for(int i = 1; i < a; i++)
n *= 2;
int y, x;
scanf("%d", &y);
scanf("%d", &x);
int answer = 0;
while(n >= 1){
if (y >= n/2 && x >= n/2)
answer += n*n - (n/2)*(n/2);
else if (y >= n/2 && x < n/2)
answer += n*n - 2*(n/2)*(n/2);
else if (y < n/2 && x >= n/2)
answer += n*n - 3*(n/2)*(n/2);
else if (y < n/2 && x < n/2)
answer += n*n - 4*(n/2)*(n/2);
if (n == 1)
break;
y = y % (n/2);
x = x % (n/2);
n /= 2;
}
printf("%d", answer - 1);
}
간만에 C로 풀었다.
이거 어렵다.
발상이 정말 어렵다. 5시간 걸렸다.
핵심은 '분할'이다. 가장 큰 사각형부터 2X2 사각형까지 Z자로 연산이 계속된다는 점을 파악한 후,
사각형을 계속 4등분 하면서 적절한 연산을 해주면 되는데,
2차원 배열의 인덱스가 n/2의 값을 가지는 4등분 된 사각형 안에서 다시 어떤 인덱스를 가지는 지 생각하는 게 정말 어려웠다.
해답은 나머지 연산.
좌표에 대해서 n으로 나머지 연산을 시행하면
사각형을 분할했을 때 그 사각형을 기준으로 상대적인 좌표의 위치를 알 수 있다.
'알고리즘-문제' 카테고리의 다른 글
구름톤 챌린지 4주 차 문제 17 학습 일기 (0) | 2024.02.18 |
---|---|
백준 1436 영화감독 숌 (0) | 2024.02.18 |
백준 1753 최단경로 (0) | 2024.02.18 |
백준 숫자카드 2 java (0) | 2024.02.18 |
[C] 백준 9663번 N-Queen : 네이버 블로그 (0) | 2024.02.18 |