Mini
백준 1074 Z C++ // 재귀 본문
https://www.acmicpc.net/problem/1074
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을
www.acmicpc.net
1. 왜 재귀로 푸나?
새로운 값을 구할때 이전의 값을 활용한다.
2. 함수정의
3. 기저사례
4. 재귀식
#include <bits/stdc++.h>
using namespace std;
//2^n * 2^n 배열에서 , (r,c) 방문순서 반환
int func(int n, int r, int c) {
//기저사례 : 1x1 칸의 번호는 0이다.
if (n == 0) return 0;
int half = 1 << (n - 1); //2^(n-1)임.
//좌측위의경우
//이전구역이 총 몇칸인지 해당 값 + 다시4분할해서 재귀
if (r < half && c < half) {
return func(n - 1, r, c);
}
if (r < half && c >= half) {
return half * half + func(n - 1, r, c - half);
}
if (r >= half && c < half){
return 2 * half * half + func(n - 1, r - half, c);
}
if (r >= half && c >= half) {
return 3 * half * half + func(n - 1, r - half, c - half);
}
}
int main() {
ios_base::sync_with_stdio(0);
cout.tie(0); cin.tie(0);
int n, r, c;
cin >> n >> r >> c;
cout << func(n, r, c);
return 0;
}
'Algorithm > recursion' 카테고리의 다른 글
| 백준 2630 색종이 만들기 c++ // 재귀함수 , 일반식만들기 (0) | 2023.09.26 |
|---|---|
| 백준 1780 종이의 개수 c++ // 재귀함수, 일반식도출 (0) | 2023.09.26 |
| 백준 17478 재귀함수가 뭔가요? c++ // 재귀함수 callback은 재귀호출뒤에쓰면된다. (0) | 2023.09.23 |
| 백준 1629 곱셈 c++ // 재귀함수 (0) | 2023.09.22 |
| 프로그래머스 하노이의 탑 c++ // 재귀함수 (0) | 2023.09.22 |