[it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비] 2차원 배열 탐색 - 블록의 최댓값(2차원 배열 응용)

문제

현수는 블록놀이를 좋아합니다. 현수에게 정면에서 본 단면과 오른쪽 측면에서 본 단면을 주 고 최대 블록개수를 사용하여 정면과 오른쪽 측면에서 본 모습으로 블록을 쌓으라 했습니다. 현수가 블록을 쌓는데 사용해야 할 최대 개수를 출력하는 프로그램을 작성하세요.
위에서 봤을 때 각 칸의 블록의 개수입니다. 정면에서의 높이 정보와 오른쪽 측면에서의 높이 정보가 주어지면 사용할 수 있는 블록의 쵀대 개수를 출력하세요.

💡 입력설명
첫 줄에 블록의 크기 N(3<=N<=10)이 주어집니다. 블록이 크기는 정사각형 N*N입니다.
두 번째 줄에 N개의 정면에서의 높이 정보가 왼쪽 정보부터 주어집니다.
세 번째 줄에 N개의 오른쪽 측면 높이 정보가 앞쪽부터 주어집니다.
블록의 높이는 10 미만입니다.

💡 출력설명
첫 줄에 블록의 최대 개수를 출력합니다.

💡 입력예제
4
2 0 3 1
1 1 2 3

💡 출력예제
17

 

---

코드

최종 풀이

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n, i, j, pos = 0, sum = 0;
	scanf("%d", &n);
	vector<vector<int> >a(n + 1, vector<int> (n + 1, 0));
	int front[n + 1] = {};
	int right[n + 1] = {};

// front 입력 
	for(i = 1; i <= n; i++) {
		scanf("%d", &front[i]);
	}
//	right 입력 
	for(i = 1; i <= n; i++) {
		scanf("%d", &right[i]);
	}
	
//	값 할당 
	for(i = n; i >= 1; i--) {
		pos++;
		for(j = 1; j <= n; j++) {
			if(right[pos] <= front[j]) {
				a[i][j] = right[pos];
			} else if(front[j] == 0) {
				a[i][j] = 0;
			} else {
				a[i][j] = front[j];
			}
		}
	}

// 합 계산 
	for(i = 1; i <= n; i++) {
		for(j = 1; j <= n; j++) {
			sum += a[i][j];
		}
	}
	printf("%d", sum);
	return 0;
}

 

---

설명

정사각형 n*n크기의 블록을 만들기 위해 사용자로부터 n을 입력받고 n + 1크기 만큼의 2차원 배열을 0으로 초기화해놓는다.

측면과 정면의 값을 따로 front, right 배열에 할당한다.

2차원 배열의 정면을 시작으로(n)해서 맨 뒤쪽까지 할당받는 식으로 접근하여 측면의 값과 정면의 값을 서로 비교하면서 값을 할당한다.

측면의 값이 정면의 값보다 작을 경우 측면의 값을 블록의 할당하고 만약 정면의 값이 0일 경우 0을 할당한다. 나머지 정면의 값이 더 클우 해당 측면의 값을 할당한다.

할당한 값의 2차원 배열을 탐색하여 값의 합을 sum에 할당하고 출력하여 마무리한다.

 

---

배운 점

기존의 2차원 배열에서 a[i][j]순으로 탐색하면 행 방향으로 탐색하였지만 i, j를 서로 바꾸어 a[j][i]로 탐색할 경우 열 방향으로 탐색한다는 것을 알 수 있었다.

 

---

 

해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.