BOJ/백준 17829 222-폴링

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

 

해결 아이디어

배열을 쪼개서 문제를 해결 해야하는 것을 보니 재귀적으로 접근하면 해결이 될 것 같아서 우선 재귀적으로 접근하고

우리가 구해야하는 것은 값일 뿐이니 배열을 갱신 하지는 않고 값만 리턴해서 정답을 구하면 될것 같았다

 

재귀적 접근

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

int solve(vector<vector<int>>& v, int size, int x, int y){
    if(size == 2){
        vector<int> tmp;
        for(int i = x; i < x + size; i++){
            for(int j = y; j < y + size; j++){
                tmp.push_back(v[i][j]);
            }
        }
        sort(tmp.begin(), tmp.end());
        return tmp[2];
    }
    else{
        int halfSize = size / 2;
        vector<int> tmp;
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < 2; j++){
                tmp.push_back(solve(v, halfSize, x + i * halfSize, y + j * halfSize));
            }
        }
        sort(tmp.begin(), tmp.end());
        return tmp[2];
    }
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> v(n, vector<int> (n));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> v[i][j];
        }
    }
    cout << solve(v, n, 0, 0);
    return 0;
}

배열을 쪼개서 값을 갱신하면서 계산

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

// 주어진 2x2 블록에서 두 번째로 큰 값을 찾는 함수
int calc(int a, int b, int c, int d) {
    vector<int> tmp = {a, b, c, d};
    sort(tmp.begin(), tmp.end());
    return tmp[2];
}

int main() {
    int n;
    cin >> n;

    // NxN 행렬 입력
    vector<vector<int>> v(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> v[i][j];
        }
    }

    // 2x2 풀링 연산을 반복적으로 수행
    while (n > 1) {
        // 새로운 (N/2)x(N/2) 행렬로 변환
        vector<vector<int>> newV(n / 2, vector<int>(n / 2));
        for (int i = 0; i < n; i += 2) {
            for (int j = 0; j < n; j += 2) {
                // 현재 2x2 블록에서 두 번째로 큰 값을 찾아서 새로운 행렬에 저장
                newV[i / 2][j / 2] = calc(v[i][j], v[i][j+1], v[i+1][j], v[i+1][j+1]);
            }
        }
        // 행렬 크기를 절반으로 줄임
        v = newV;
        n /= 2;
    }

    // 마지막 남은 값 출력
    cout << v[0][0] << endl;

    return 0;
}

 

위가 반복문을 통해 해결 아래가 재귀적으로 해결

재귀적으로 해결한게 시간이 절반 수준인 것을 확인 할 수 있다.

 

그러고보니 sort를 하면 오름차순인데 내림차순으로 착각해버려서 tmp[1]을 해놓고 왜 값이 안나오는지 생각하다 sort한 결과를

콘솔에 찍어본다음 해결했다.... 푸는데 약 30분 넘게 걸린거 같은데 코테칠 수준까지 올리려면 아직 갈길이 먼것 같다.