# 생각
N(1<= N <= 15)이 주어졌을 때,
2^n * 2^n 배열에서 (r, c)를 방문하는 순서를 출력하는 프로그램을 작성해야 한다
규칙을 보면 배열을 4등분 하여 순서대로 진행하는 것을 알 수 있다
base conditino은 n이 0일 때 return해주는게 좋아보인다
재귀식은 규칙에 따라 4등분하여 각 상황에 맞게 반환해주면 된다
# 전체 코드
#include <bits/stdc++.h>
using namespace std;
int ZRecursive(int n, int r, int c)
{
if (n == 0)
{
return 0;
}
int half = 1 << (n - 1);
if (r < half && c < half) // 왼쪽 위
{
return ZRecursive(n - 1, r, c);
}
if (r < half && c >= half) // 오른쪽 위
{
return (half * half) + ZRecursive(n - 1, r, c - half);
}
if (r >= half && c < half) // 왼쪽 아래
{
return (2 * half * half) + ZRecursive(n - 1, r - half, c);
}
else // 오른쪽 아래
{
return (3 * half * half) + ZRecursive(n - 1, r - half, c - half);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, r, c;
cin >> N >> r >> c;
cout << ZRecursive(N, r, c);
}
https://www.acmicpc.net/problem/1074
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을
www.acmicpc.net
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 2630_색종이 만들기 with cpp (0) | 2022.01.28 |
---|---|
[BOJ] 17478_재귀함수가 뭔가요? with cpp (0) | 2022.01.27 |
[BOJ] 11729_하노이 탑 이동 순서 with cpp (0) | 2022.01.27 |
[BOJ] 1629_곱셈 with cpp (0) | 2022.01.25 |
[BOJ] 5427_불 with cpp (0) | 2022.01.25 |