Search
Duplicate

Z

주차
0
문제번호
1074
언어
C++
티어
실버
유형
분할 정복
재귀
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

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++
복사