[백준] 17829 222-풀링, python, C++

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

17829번: 222-풀링

분할 정복문제이다.

두번째로 큰 값을 찾고, 새로운 이차원 행렬을 계속 만드는 방식으로

# import sys; input = sys.stdin.readline

def second_max(r, c, arr):
    s = [arr[r][c], arr[r][c + 1], arr[r + 1][c], arr[r + 1][c + 1]]
    s.sort()
    s.pop()
    return s.pop()

def create_arr(arr):
    size = len(arr) // 2
    new_arr = [[0 for _ in range(size)] for _ in range(size)]
    for i in range(size):
        for j in range(size):
            new_arr[i][j]= second_max(2 * i, 2 * j, arr)
    return new_arr

def main():
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    while len(arr) != 1:
        arr = create_arr(arr)
    print(arr[0][0])

if __name__ == '__main__':
    main()

 

인덱스 접근으로 특정 인덱스만 갱신하는 방법이다.

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

int arr[1024][1024] = { 0 };

int find_second_max(int r, int c, int size) {
    int tmp[4] = { arr[r][c], arr[r + size][c], arr[r][c + size], arr[r + size][c + size] };
    sort(tmp, tmp + 4);
    return tmp[2];
}
int main() {
    // 0 init
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, i, j, size, tmp_i, tmp_j;
    // 1 input
    cin >> N;
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            cin >> arr[i][j];

    // 2 222 pulling
    size = N;
    while (size != 1) {
        for (i = 0; i < size / 2; i++) {
            for (j = 0; j < size / 2; j++) {
                tmp_i = N / size * i * 2;
                tmp_j = N / size * j * 2;
                arr[tmp_i][tmp_j] = find_second_max(tmp_i, tmp_j, N / size);
            }
        }
        size >>= 1;
    }
    // 3 output
    cout << arr[0][0] << '\n';

    return 0;
}