[알고리즘] 백준 17829번: 222-풀링 (C++)

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

17829번: 222-풀링

오랜만에 푼 분할 정복 문제였다.

헷갈렸던 부분은 함수를 구현할 때였는데

int dq(int num, int i, int j){
    if(num == 1){
        return arr[i][j];
    }
    
    int temp[5];
    temp[1] = dq(num / 2, i, j);
    temp[2] = dq(num / 2, i + num / 2, j);
    temp[3] = dq(num / 2, i, j + num / 2);
    temp[4] = dq(num / 2, i + num / 2, j + num / 2);
    
    sort(temp + 1, temp + 5);
    return temp[3];
}

이렇게 구현했어야 하는 걸

int dq(int num, int i, int j){
    if(num == 1){
        return arr[i][j];
    }
    
    int temp[5];
    temp[1] = dq(num / 2, 1, 1);
    temp[2] = dq(num / 2, 1 + num / 2, 1);
    temp[3] = dq(num / 2, 1, 1 + num / 2);
    temp[4] = dq(num / 2, 1 + num / 2, 1 + num / 2);
    
    sort(temp + 1, temp + 5);
    return temp[3];
}

i와 j의 자리를 1로 작성하여 왼쪽 상단 박스에서만 값을 가져오게 했었다.

그러다 보니 제일 작은 예시 

2
3 4
2 1

로 주었을 때 알아차리지 못했다.

---

[AC 코드]

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int arr[1025][1025];

int dq(int num, int i, int j){
    if(num == 1){
        return arr[i][j];
    }
    
    int temp[5];
    temp[1] = dq(num / 2, i, j);
    temp[2] = dq(num / 2, i + num / 2, j);
    temp[3] = dq(num / 2, i, j + num / 2);
    temp[4] = dq(num / 2, i + num / 2, j + num / 2);
    
    sort(temp + 1, temp + 5);
    return temp[3];
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> arr[i][j];
        }
    }
    
    cout << dq(n, 1, 1);
    return 0;
}