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

17829번: 222-풀링 (acmicpc.net)

17829번: 222-풀링

다른 문제를 풀다가.. 틀렸습니다에 고생하고 있다. 그래서 머리 식힐 겸 실버 문제를 풀어봤다. (그런데 한번 틀렸다 ㅎ)

이 문제가 가장 쉬운 형태의 분할 정복 문제 중의 하나라고 생각한다.

---

문제 풀이

분할 정복을 적용하면 쉽게 문제를 통과할 수 있다.

 

단순하게 큰 행렬(matrix)를 \(2 \times 2\) 크기로 나눠서 두 번째로 큰 값을 뽑아낸다. 그렇게 뽑아낸 값들로 새로운 행렬을 만들기를 반복하면 된다.

 

문제를 한 번 틀렸는데, 주어진 행렬의 크기가 \(N \times N \) 일 때, 새롭게 생성된 행렬의 크기는 \({N \over 2} \times {N \over 2}\)의 크기가 되어야 한다. 근데 이 크기를 잘못 적어 주어진 행렬의 크기와 동일한 \(N \times N \) 크기로 생성을 해서 런타임 오류가 발생했다.

#include <cstdio>
#include <algorithm>
#include <vector>

void inputMatrix();
int polling(const std::vector<std::vector<int> > &matrix);

const int STEP = 2;
int N;
std::vector<std::vector<int> > matrix;

int main(void) {
	inputMatrix();
	int result = polling(matrix);
	printf("%d", result);
	return 0;
}

void inputMatrix() {
	::scanf("%d", &N);

	matrix.resize(N);
	for ( int i = 0; i < N; ++i ) {
		matrix[i].resize(N);

		for ( int j = 0 ; j < N; ++j ) {
			int val = 0;
			::scanf("%d", &val);
			matrix[i][j] = val;
		}
	}
}

int getSecondBiggest(const std::vector<std::vector<int> > &matrix, const int startY, const int startX) {
	std::vector<int> tmp;
	for ( int stepY = 0; stepY < STEP; ++stepY ) {
		for ( int stepX = 0; stepX < STEP; ++stepX ) {
			tmp.push_back(matrix[startY + stepY][startX + stepX]);
		}
	}

	std::sort(tmp.rbegin(), tmp.rend());
	return tmp[1];
}

int polling(const std::vector<std::vector<int> > &matrix) {
	const size_t len = matrix.size();
	if ( 2 == len ) {
		return getSecondBiggest(matrix, 0, 0);
	}

	const size_t sublen = (len >> 1);
	std::vector<std::vector<int> > submatrix(sublen, std::vector<int>(sublen));
	for ( int y = 0; y < sublen; ++y ) {
		for ( int x = 0; x < sublen; ++x ) {
			submatrix[y][x] = getSecondBiggest(matrix, y * 2, x * 2);
		}
	}
	return polling(submatrix);
}