관리 메뉴

KoreanFoodie's Study

SW 역량테스트 - [백준] 원판 돌리기 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

SW 역량테스트 - [백준] 원판 돌리기 문제 풀이/해답/코드 (C++ / JAVA)

hashnut 2020. 10. 15. 23:54


SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 


문제 링크 : www.acmicpc.net/problem/17822

해답 코드 : 

 

#include <iostream>
#include <deque>

using namespace std;

typedef struct plate{
	int num;
	bool mark;
}plate;

typedef struct inst {

	int pl;
	int dir;
	int tile;

}inst;

int N, M, T;

deque<plate> plates[51];
inst insts[51];

int dR[4] = { -1, 1, 0, 0 };
int dC[4] = {0, 0, -1, 1};

// clockwise turn of 'k'th plate
void clockwise(int k) {

	plate t_pl = plates[k][plates[k].size() - 1];
	plates[k].pop_back();
	plates[k].push_front(t_pl);

}
// counter-clockwise turn of 'k'th plate
void c_clockwise(int k) {
	plate t_pl = plates[k][0];
	plates[k].pop_front();
	plates[k].push_back(t_pl);
}

// check adjacent numbers in a plate
// check adjacent numbers in 4 directions
// mark adjacent values to 'true'
// if adjacent number exist, return true;
bool check_adj() {
	
	int c_n, n_n;
	bool flag = false;

	for (int i = 1; i <= N; i++) {

		// check adjacent numbers in a plate
		for (int j = 0; j < M; j++) {
			c_n = plates[i][j].num;
			n_n = plates[i][(j+1)%M].num;

			if (c_n != -1 && c_n == n_n) {
				plates[i][j].mark = true;
				plates[i][(j + 1) % M].mark = true;
				flag = true;
			}
		}
	}

	// check adjacent numbers in 4 directions
	for (int j = 0; j < M; j++) {

		for (int i = 1; i <= N-1; i++) {
			c_n = plates[i][j].num;
			n_n = plates[i+1][j].num;

			if (c_n != -1 && c_n == n_n) {
				plates[i][j].mark = true;
				plates[i+1][j].mark = true;
				flag = true;
			}
		}
	}
	return flag;
}

// restore 'mark' value to false
void restore_adj() {
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			plates[i][j].mark = false;
		}
	}
}

// for all numbers in plates :
// if mark == true, make it 0
void mark_zero() {
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			if (plates[i][j].mark) {
				plates[i][j].num = -1;
			}
		}
	}
}

// return summed number of plates
int sum_pl() {
	int sum = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {

			if (plates[i][j].num >= 0) {
				sum += plates[i][j].num;
			}
		}
	}

	return sum;
}

// no adjacent numbers -> avg_out, +-1 except 0.
void avg_out() {
	
	double sum = 0;
	double total = 0;
	double avg;

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {

			if (plates[i][j].num >= 0) {
				sum += plates[i][j].num;
				total++;
			}

		}
	}
	avg = sum / total;

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {

			if (plates[i][j].num > avg) {
				
				plates[i][j].num--;

			}
			else if (plates[i][j].num >= 0 && plates[i][j].num < avg) {
				plates[i][j].num++;
			}

		}
	}

}

// call this each time
void rotate(int i_n, int i_d, int i_t) {
	
	int t_n, t_d, t_t;

	for (int i = 1; i <= N; i++) {

		// rotate (pick)
		if (i % i_n == 0) {

			// rotate i_t times
			for (int rot = 0; rot < i_t; rot++) {
				// direction
				if (i_d == 0) {
					clockwise(i);
				}
				else {
					c_clockwise(i);
				}
			}

		}
	}

	if (check_adj()) {
		mark_zero();
	}
	else {
		avg_out();
	}

	restore_adj();

}


int main() {

	cin >> N >> M >> T;

	int t_n, t_d, t_t;
	plate t_pl;
	inst t_ins;
	int t;

	for (int i = 1; i <= N; i++) {

		for (int j = 0; j < M; j++) {

			cin >> t_n;
			t_pl = {t_n, false};
			plates[i].push_back(t_pl);

		}
	}

	for (int i = 1; i <= T; i++) {
		cin >> t_n >> t_d >> t_t;
		//t_ins = {t_n, t_d, t_t};
		insts[i] = { t_n, t_d, t_t };
	}

	for (t = 1; t <= T; t++) {
		t_n = insts[t].pl;
		t_d = insts[t].dir;
		t_t = insts[t].tile;
		rotate(t_n, t_d, t_t);
	}

	cout << sum_pl() << endl;
}

 

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제

 
0 Comments
댓글쓰기 폼