[BOJ 17829 // C++] 222-풀링

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17829번 문제인 222-풀링이다.
문제는 아래 링크를 확인하자.

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

17829번: 222-풀링

2N*2N 정사각형을 N*N 정사각형으로 바꾸는 방법을 먼저 생각한 뒤, 이것을 N이 1이 될 때까지 반복하는 코드를 작성하는 것으로 이 문제를 간단히 해결할 수 있다.

 

r행c열부터 r+1행c+1열까지의 사각형으로 얻은 정보를 r/2행c/2열에 저장하는 식으로 구현하면 구현이 간단해진다. 이와 같이 저장하여도 지워지는 데이터는 이미 확인을 마친, 다시 살펴볼 일이 없는 데이터이므로 문제가 생기지 않는다.

 

아래는 제출한 소스코드이다.

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

int arr[1024][1024];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> arr[r][c];
		}
	}

	while (N > 1) {
		for (int r = 0; r < N; r+=2) {
			for (int c = 0; c < N; c += 2) {
				vector<int> tmp;
				tmp.emplace_back(arr[r][c]);
				tmp.emplace_back(arr[r + 1][c]);
				tmp.emplace_back(arr[r][c + 1]);
				tmp.emplace_back(arr[r + 1][c + 1]);
				sort(tmp.begin(), tmp.end());
				arr[r >> 1][c >> 1] = tmp[2];
			}
		}
		N >>= 1;
	}

	cout << arr[0][0];
}