반응형 1시간12분1 [BaekJoon/백준] 1074번 C++ 분할정복 분할정복 관련 문제다. 하지만 주의사항이 있다. 분할정복은 맞는데, 분할정복으로 모든 곳을 돌아서 값을 채우고, 그 배열을 이용하려 하면 시간초과가 날 것이다. 최대크기 32568 x 32578은 10억이 넘는다. 시간복잡도 O(n)에서 10억이면 10초정도 예상된다. 따라서 분할했을 때, 해당 섹션을 방문하지 않고도, 계산에 문제가 없도록 섹션의 크기를 계산해내는것이 중요하다. 문제에서 n을 입력 받을 때 변의 길이 = 2^n 역할의 n을 입력받으므로 1. 4^(n - 1)을 구역(섹션) 당 크기로 계산해도 되겠고 2. (현재 변의 길이 / 2)^2 을 구역 당 크기로 계산해도 되겠다. #include #include #include using namespace std; int N, C, i, j; i.. 2021. 3. 23. 이전 1 다음 반응형
