재귀 함수 문제를 풀기 전에
다음과 같은 세부 사항을 잘 정리해나가면 푸는 데에 많은 도움이 된다.
1. 함수의 정의
2. base condition
3. 재귀 식
문제 링크
[1074 Z]
접근
딱 봐도 반복되는 모양을 보아하니 재귀를 쓰면 알맞을 것 같았다. 하지만 재귀 함수를 써야 한다는 건 알아도 어떻게 써야 하는지는 잘 몰랐기 때문에 위의 세부 사항을 정리해 보았다.
1. 함수의 정의
직관적으로 정의하면 된다.
// 2^n * 2^n 배열에서 (r, c)를 방문하는 순서를 반환하는 함수
int func(int n, int r, int c)
2^n이 int 범위 안에 들어오는지도 신경을 써야 한다. 문제에서 n이 15 이하라고 했으니 범위에 잘 맞다.
2. base condition
if(n == 0) return 0;
3. 재귀 식
// 함수 정의
// 2^n * 2^n 배열에서 (r, c)를 방문하는 순서를 반환하는 함수
int func(int n, int r, int c)
// (r, c)가 1번 사각형일 때
return func(n - 1, r, c);
// (r, c)가 2번 사각형일 때
return half * half + func(n - 1, r, c - half);
// (r, c)가 3번 사각형일 때
return 2 * half * half + func(n - 1, r - half, c);
// (r, c)가 4번 사각형일 때
return 3 * half * half + func(n - 1, r - half, c - half);
여기서 half는 한 변 길이의 절반, 즉 2^(n-1)이다. 2번 사각형의 half * half는 1번 사각형의 개수를 더한 것이다. 이후 같은 방법으로 진행한다.
코드
#include <iostream>
using namespace std;
int Solve(int n, int r, int c)
{
if (n == 0) return 0;
int half = 1 << (n - 1);
// 1번 사각형
if (r < half && c < half)
return Solve(n - 1, r, c);
// 2번 사각형
if (r < half && c >= half)
return half * half + Solve(n - 1, r, c - half);
// 3번 사각형
if (r >= half && c < half)
return 2 * half * half + Solve(n-1, r - half, c);
// 4번 사각형
if (r >= half && c >= half)
return 3 * half * half + Solve(n-1, r - half, c - half);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, r, c;
cin >> n >> r >> c;
cout << Solve(n, r, c);
return 0;
}
결과
참고 블로그
'알고리즘' 카테고리의 다른 글
[C++] Boj 17478 재귀함수가 뭔가요? (0) | 2025.01.09 |
---|---|
[C++] Boj 9466 텀 프로젝트 (0) | 2025.01.08 |
[C++] Boj 1629 곱셈 (0) | 2025.01.07 |
[C++] Boj 2573 빙산 (0) | 2025.01.06 |
[C++] Boj 2146 다리 만들기 (0) | 2025.01.06 |