Memo
로직 설명
•
재귀적으로 함수를 구현했습니다. 인자로 넘어온 현재 길이를 토대로 4분면을 만들고, (r,c) 의 위치를 수식을 통해 어느 사분면에 위치한지 찾습니다.
•
해당 사분면으로 들어갈 수 있도록, 조건문을 적절히 걸어줍니다.
⇒ 일반적인 divide and conquer 방식으로 코드를 작성하면 시간초과가 발생합니다. 이는 시간복잡도가 2^15 * 2^15 정도 나오게 되는데, 이는 약 10억 정도가 되므로 제한 시간안에 답을 구해낼 수는 없습니다.
시간 초과 발생 코드
Code
제출 날짜
@4/27/2021
메모리
2200 KB
시간
0 ms
#include <iostream>
#include <cmath>
int N, r, c;
int cnt;
void io_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
io_faster();
std::cin >> N >> r >> c;
}
void dc(int y, int x, int len)
{
if (y == r && x == c)
return;
if (y <= r && r < y + len/2 && x <= c && c < x + len / 2)
dc(y, x, len / 2);
else if (y <= r && r < y + len / 2 && x + len / 2 <= c && c < x + len)
{
cnt += (std::pow(len / 2, 2));
dc(y, x + len / 2, len / 2);
}
else if (y + len / 2 <= r && r < y + len && x <= c && c < x + len / 2)
{
cnt += 2 * (std::pow(len / 2, 2));
dc(y + len / 2, x , len / 2);
}
else
{
cnt += 3 * (std::pow(len / 2, 2));
dc(y + len / 2, x + len / 2, len / 2);
}
}
void solve()
{
dc(0, 0, std::pow(2, N));
}
void print_val()
{
std::cout << cnt;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사