백준 17829, 222-풀링

문제

https://www.acmicpc.net/problem/17829

풀이 방법

간단하게 하나의 재귀 함수를 자기가 확인해야 하는 영역의 크기(n)을 입력받고 해당 영역을 4개로 나눠 2번째로 큰 값을 return하게 만들었다.

시간복잡도는 함수 호출 횟수 * 함수에서 걸린 시간인데 함수에서 걸린 시간은 상수 시간이므로 총 함수 호출 횟수는 1 + 4^1 + ... + 4^20 인데 약 4^20이므로 시간내에 돌아간다. (O(n^2))

실수

• 처음에 문제를 이해하지 못해서 (자신의 용어로 재정의) 이해하고 작성하는데 생각보다 많은 시간이 들어갔다. 문제를 무작정 풀려하지 말고 이해하고 재정의, 추상화 하는 과정을 잘해보자.
• 실수는 아닌데 벡터로 바꾸니까 시간이 늘어나더라 1/100 정도

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector <vector<int>> arr(1100, vector<int>(1100, 0));

int solve(int n, int x, int y) { // n은 확인 하는 영역의 한 변의 길이, x, y는 시작 위치, 해당하는 영역을 4개로 나눠 2번째로 큰 값을 return

    if (n == 1) {

        return arr[x][y];

    }

    else {

        int sort_arr[4];

        sort_arr[0] = solve(n / 2, x, y);

        sort_arr[1] = solve(n / 2, x + n / 2, y);

        sort_arr[2] = solve(n / 2, x, y + n / 2);

        sort_arr[3] = solve(n / 2, x + n / 2, y + n / 2);

        sort(sort_arr, sort_arr + 4);

        return sort_arr[2];

    }


}

int main() {

    int n;

    cin >> n;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            cin >> arr[i][j];

        }

    }

    cout << solve(n, 0, 0);

    return 0;

}