[백준 17140] 이차원 배열과 연산

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

17140번: 이차원 배열과 연산

요구사항

1. map[r][c]에 k가 나올때까지 r연산, c연산 하기

 

풀이

1. R, C 연산 둘 중에 무엇을 할지 판단

2. R연산 실시

 - 문제에서 주어진 대로 많이 나오는 순, 큰 수 대로 정렬을 해서 map에 넣을 수 있도록 한다.

 - 숫자 횟수 확인 시, map 0으로 초기화

3. C연산 실시

4. 답인지 확인 하기

 

차근차근 풀어보면 어렵지 않은 문제

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
struct go {
	int x;
	int y;
};
int r, c, k;
int map[101][101];
int visit[101];
int M=3;
int N=3;
int ans = 0;
bool com(go a, go b) {
	//숫자 나타난 횟수
	if (a.y < b.y) {
		return true;
	}
	else if (a.y == b.y) {
		if (a.x < b.x)
			return true;
	}
	return false;
}
void solve() {
	if (map[r][c] == k){
		ans = 0;
		return;
	}
	int cnt = 0;
	while (true) {
		cnt++;
		if (cnt > 100){
			ans = -1;
			return;
		}
		if (N >= M) {
			for (int i = 0; i < N; i++) {
				memset(visit, 0, sizeof(visit));
				vector<go> v;
				int Maxnum = 0;
				for (int j = 0; j < M; j++) {
					if (map[i][j] == 0)
						continue;
					else {
						visit[map[i][j]]++;
						Maxnum = max(Maxnum, map[i][j]);
					}
					map[i][j] = 0;
				}
				for (int j = 1; j <= Maxnum; j++) {
					if (visit[j] == 0)
						continue;
					else
						v.push_back({ j,visit[j] });
				}
				sort(v.begin(), v.end(), com);
				//이제 map에 넣기
				int s = v.size();
				if (s > 49) {
					s = 49;
				}
				int nn = 0;
				for (int j = 0; j < s; j++) {
					map[i][nn++] = v.at(j).x;
					map[i][nn++] = v.at(j).y;
				}
				M = max(M, nn);
			}
		}
		else {
			for (int i = 0; i < M; i++) {
				memset(visit, 0, sizeof(visit));
				vector<go> v;
				int Maxnum = 0;
				for (int j = 0; j < N; j++) {
					if (map[j][i] == 0)
						continue;
					else {
						visit[map[j][i]]++;
						Maxnum = max(Maxnum, map[j][i]);
					}
					map[j][i] = 0;
				}
				for (int j = 1; j <= Maxnum; j++) {
					if (visit[j] == 0)
						continue;
					else
						v.push_back({ j,visit[j] });
				}
				sort(v.begin(), v.end(), com);
				//이제 map에 넣기
				int s = v.size();
				if (s > 49) {
					s = 49;
				}
				int nn = 0;
				for (int j = 0; j < s; j++) {
					map[nn++][i] = v.at(j).x;
					map[nn++][i] = v.at(j).y;
				}
				N= max(N, nn);
			}
		}
		if (map[r][c] == k) {
			ans = cnt;
			return;
		}
	}
}
int main() {
	cin >> r >> c >> k;
	r -= 1;
	c -= 1;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> map[i][j];
		}
	}
	solve();
	cout << ans << endl;
	
}