재귀함수를 사용하는 문제이다. 재귀함수는 아무리 풀어도 익숙해지지가 않는듯하다
사실 이 문제는 재귀함수를 따로 정의하기 보다 while문 돌리는게 편했다.
1. 재귀함수 사용
기저 조건은 한 변의 길이가 2인 정사각형일때이다.
cnt의 초기값을 0으로 설정하여 기저 조건에 도달할 때마다 4씩 더해준다.
재귀함수 내 재귀함수 호출은 z모양으로 발생한다.
#include <stdio.h>
using namespace std;
int n, r, c, cnt;
void fillZ(int len, int row, int col)
{
if (len == 2)
{
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
if (row + i == r && col + j == c)
{
printf("%d\n", cnt);
return;
}
cnt++;
}
}
return;
}
len = len / 2;
fillZ(len, row, col);
fillZ(len, row, col + len);
fillZ(len, row + len, col);
fillZ(len, row + len, col + len);
}
int main(void)
{
scanf("%d%d%d", &n, &r, &c);
fillZ(1 << n, 0, 0);
return 0;
}
2. while문 사용
전체 길이 len = 1<<n에서 r과 c의 위치를 찾는다.
len의 중간지점인 mid를 중심으로 r과 c를 재조정하고 cnt도 더해준다.
1, 2, 3, 4 순으로 확인하며 1의 경우 어떠한 값도 변화하지 않고 총 길이만 변화시킨다.
#include <stdio.h>
using namespace std;
int n, r, c, cnt;
int main(void)
{
scanf("%d%d%d", &n, &r, &c);
int len = 1 << n;
while (len > 1)
{
int mid = len / 2;
if (r < mid && c >= mid)
{
c -= mid;
cnt += mid * mid;
}
else if (r >= mid && c < mid)
{
r -= mid;
cnt += mid * mid * 2;
}
else if (r >= mid && c >= mid)
{
r -= mid;
c -= mid;
cnt += mid * mid * 3;
}
len = mid;
}
printf("%d\n", cnt);
return 0;
}
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 1629] 곱셈 (1) | 2020.12.13 |
---|---|
[백준 1495] 기타리스트 (0) | 2020.12.13 |
[백준 1992] 쿼드트리 (0) | 2020.12.13 |
[백준 5904] Moo 게임 (0) | 2020.12.12 |
[백준 1780] 종이의 개수 (0) | 2020.12.12 |
댓글