[백준,c++] 17829번 - 222-풀링

문제

17829번: 222-풀링

 

코드

// 13:00 ~ 13:50
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

vector<vector<int>>v;
int N;

int dx[3] = {1,0,1};
int dy[3] = {0,1,1};

int find(int i, int k){
    priority_queue<int>pq;
    pq.push(v[i][k]);
    for(int j=0; j<3; j++){
        int nx = i+dx[j];
        int ny = k+dy[j];
        pq.push(v[nx][ny]);
    }
    pq.pop();
    return pq.top();
}

vector<vector<int>> divide(vector<vector<int>> &v, int n){
    
    vector<vector<int>>fin;
    
    for(int i=0; i<n; i+=2){
        vector<int>ing;
        for(int k=0; k<n; k+=2){
            ing.push_back(find(i,k));
        }
        fin.push_back(ing);
    }
    
    return fin;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N;
    
    for(int i=0; i<N; i++){
        vector<int>temp;
        for(int k=0; k<N; k++){
            int inp; cin>>inp;
            temp.push_back(inp);
        }
        v.push_back(temp);
    }
    
    while(v.size()!=1){
        vector<vector<int>>temp =divide(v, v[0].size());
        v = temp;
    }
    
    cout<<v[0][0];
}

 

풀이

2번째로 큰 수를 찾는 건데 대충 읽고 제일 큰 수를 찾다가 시간을 소비했습니다.

 

분할하여 푸는 구현 문제였는데 2x2 씩 나누어서 찾기 때문에 배열에 접근하는 인덱스를 i+2, k+2씩 해줘 가며 기준점을 잡았고 그 기준점으로부터 오른쪽, 아래, 오른쪽 아래 대각선을 찾아서 힙에 넣고, 두 번째로 작은 값을 반환해 가면서 새로운 배열을 만들었습니다. 

그리고 새로 만들 배열을 또 다시 2x2 씩 나누어 찾으며 최종적으로 배열의 크기가 1이 될 때까지 탐색했습니다.

문제를 다 풀고 다른사람의 풀이도 한번 찾아보았습니다.

(C++) - 백준(BOJ) 17829번 : 222-풀링

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int p[1025][1025];
int n,ans;
 
//두 번째로 큰 수를 반환하는 함수
int Pulling(int x, int y)
{
    vector <int > a;
    for (int i = x; i < x + 2; i++)
        for (int j = y; j < y + 2; j++)
            a.push_back(p[i][j]);
    sort(a.begin(), a.end());
    return a[2];
}
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> p[i][j];
        }
    }
    while (n > 1)
    {
        for (int i = 0; i < n; i+=2)
            for (int j = 0; j < n; j+=2)
                p[i/2][j/2] = Pulling(i,j); //가로 세로 2칸씩 움직이며 p갱신
        n /= 2;
    }
    cout << p[0][0] << '\n';
}

저처럼 새로운 배열을 생성하여 분할하지 않고 기존의 배열의 공간만 이용하여 풀으셨는데, 이게 좀 메모리 면에서는 조금 더 효율적으로 보입니다.