문제
풀이
아래 그림처럼 생각해서 재귀로 풀면 된다.
n=3, r=7, c=7인 경우의 그림이다. (빨간 체크가 내가 가야 하는 곳)
재귀 함수를 z(int n, int r, int c)라고 가정,
재귀가 돌아가는 과정을 식으로 나타내면 아래와 같다.
z(3, 7, 7)
= 3*4*4 + z(2, 3, 3)
= 48 + (3*2*2 + z(1, 1, 1))
= 48 + (12 + (3*1*1 + z(0, 0, 0)))
= 48 + 12 + 3
= 63
답안
#include <iostream>
using namespace std;
int z(int n, int r, int c) {
if (n == 0) {
return 0;
}
int half = 1 << (n-1); // 2의 n-1승
if (r < half && c < half) {
return z(n-1, r, c);
}
if (r < half && c >= half) {
return half*half + z(n-1, r, c-half);
}
if (r >= half && c < half) {
return 2*half*half + z(n-1, r-half, c);
}
return 3*half*half + z(n-1, r-half, c-half);
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n, r, c;
cin >> n >> r >> c;
cout << z(n, r, c) << '\n';
}
'백준' 카테고리의 다른 글
[9251] LCS (C++17) (1) | 2025.03.23 |
---|---|
[1463] 1로 만들기 (C++17) (0) | 2025.03.23 |
[2493] 탑 (C++17) (0) | 2025.01.20 |
[17298] 오큰수 (C++17) (0) | 2025.01.20 |
[3015] 오아시스 재결합 (C++17) (0) | 2025.01.20 |