Study hard
(c++)백준 17822번: 원판 돌리기 본문
17822번: 원판 돌리기
반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀
www.acmicpc.net
[풀이]
구현해야할 것
1. 원판
2. 원판 돌리기
3. 인접하면서 같은 수 찾기
4. 원판에 적힌 수의 평균 찾고 평균보다 큰 수에서 1 빼고 작은수에 1 더하기
1. 원판은 2차원 배열 int Circle[][]로 구현하였다. Circle[i][j]는 i번 원판의 j번째 숫자를 의미한다.
2. 돌릴 원판의 번호와 방향과 돌릴 칸 수를 인수로 보내 시계방향 또는 반시계방향으로 해당 원판을 돌리도록 하였다.
3. 같은 원판 내에서 인접하면서 같은 수를 찾고, 다른 원판들 사이에서 인접하면서 같은 수를 찾았다.
*인접하면서 같은 수는 bool check[][]에 true로 체크해놓고 같은 원판, 다른 원판 모두 살핀 다음 true로 체크된 자리의 숫자를 0으로 바꿔주었다.
4. 원판에서 0이 아닌 숫자들의 개수와 합을 구하고 합/개수 연산으로 평균을 구하였다.
*평균을 double로 구하지 않으면 답이 틀리게 된다. 문제에 소수점 아래를 버린다고 써있지 않긴 하다.
#include <iostream>
#include <vector>
using namespace std;
int N, M, T;
int Circle[51][51];//원판 숫자 저장
//n번 원판 d방향으로 k칸 회전
void TurnCircle(int n, int d, int k) {
//시계방향
if (d == 0) {
//k칸 회전
while (k--) {
int tmp = Circle[n][1];
Circle[n][1] = Circle[n][M];
for (int i = M - 1; i > 1; i--) {
Circle[n][i + 1] = Circle[n][i];
}
Circle[n][2] = tmp;
}
}
//반시계방향
else if (d == 1) {
//k칸 회전
while (k--) {
int tmp = Circle[n][M];
Circle[n][M] = Circle[n][1];
for (int i = 2; i < M; i++) {
Circle[n][i - 1] = Circle[n][i];
}
Circle[n][M - 1] = tmp;
}
}
}
//원판에 수가 남아있는지 확인
bool findNum() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (Circle[i][j] != 0)
return true;
}
}
return false;
}
bool findSame() {
bool res = false;
//없어질 숫자들 표시
bool check[51][51] = { false, };
//같은 원판에서
for (int c = 1; c <= N; c++) {
for (int n = 1; n <= M; n++) {
if (Circle[c][n] == 0)
continue;
//1번 숫자일 때
if (n == 1) {
if (Circle[c][n] == Circle[c][M]) {
check[c][n] = true;
check[c][M] = true;
}
if (Circle[c][n] == Circle[c][n + 1]) {
check[c][n] = true;
check[c][n + 1] = true;
}
}
//M번 숫자일 때
if (n == M) {
if (Circle[c][n] == Circle[c][n - 1]) {
check[c][n] = true;
check[c][n - 1] = true;
}
if (Circle[c][n] == Circle[c][1]) {
check[c][n] = true;
check[c][1] = true;
}
}
else {
if (Circle[c][n] == Circle[c][n - 1]) {
check[c][n] = true;
check[c][n - 1] = true;
}
if (Circle[c][n] == Circle[c][n + 1]) {
check[c][n] = true;
check[c][n + 1] = true;
}
}
}
}
//다른 원판에서
for (int n = 1; n <= M; n++) {
for (int c = 1; c < N; c++) {
if (Circle[c][n] == 0)
continue;
if (Circle[c][n] == Circle[c + 1][n]) {
check[c][n] = true;
check[c + 1][n] = true;
}
}
}
for (int c = 1; c <= N; c++) {
for (int n = 1; n <= M; n++) {
if (check[c][n] == true) {
Circle[c][n] = 0;
res = true;
}
}
}
return res;
}
void doElse() {
int ncnt = 0;//원판에 적힌 수의 개수
int nsum = 0;//원판에 적힌 수의 총합
//평균 구하기
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (Circle[i][j] != 0) {
ncnt++;
nsum += Circle[i][j];
}
}
}
double m = (double)nsum / (double)ncnt;//평균(소수점 아래 버리라는 말이 없음)
//평균보다 큰 수에서 1을 빼고 작은 수에 1을 더하기
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (Circle[i][j] != 0) {
if (Circle[i][j] > m) {
Circle[i][j]--;
}
else if (Circle[i][j] < m) {
Circle[i][j]++;
}
}
}
}
}
int getSum() {
int res = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
res += Circle[i][j];
}
}
return res;
}
int main() {
ios_base::sync_with_stdio(0);
cin >> N >> M >> T;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> Circle[i][j];
}
}
int x, d, k;
for (int i = 1; i <= T; i++) {
//cin >> turn[i].x >> turn[i].d >> turn[i].k;
cin >> x >> d >> k;
//번호가 x의 배수인 원판 돌리기
for (int n = x; n <= N; n += x) {
TurnCircle(n, d, k);
}
//원판에 수가 없으면
if (findNum() == false) {
cout << 0 << '\n';
return 0;
}
//인접하면서 수가 같은 것 찾기
if (findSame() == false) {//없으면
doElse();
}
}
cout << getSum() << '\n';
return 0;
}+set STL 사용한 풀이
#include <iostream>
#include <set>
using namespace std;
struct Pos{
int n;
int m;
};
int N, M, T;
int Circle[51][51];//둘 다 1부터 시작
set<pair<int,int>>Same;//인접하면서 수가 같은 것 찾아서 저장
//원판 돌리기
void Turn(int x,int d,int k) {
//번호가 x의 배수인 원판
for (int n = x; n <= N; n += x) {
//시계방향
if (d == 0) {
//k칸 회전
for (int t = 0; t < k; t++) {
int tmp = Circle[n][M];
for (int i = M - 1; i >= 1; i--) {
Circle[n][i + 1] = Circle[n][i];
}
Circle[n][1] = tmp;
}
}
//반시계방향
else if (d == 1) {
//k칸 회전
for (int t = 0; t < k; t++) {
int tmp = Circle[n][1];
for (int i = 2; i <= M; i++) {
Circle[n][i - 1] = Circle[n][i];
}
Circle[n][M] = tmp;
}
}
}
}
int Sum() {
int res = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
res += Circle[i][j];
}
}
return res;
}
bool findNum() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (Circle[i][j] > 0)
return true;
}
}
return false;
}
void findSame() {
bool check[51][51] = { false, };
//각각 원판에서 같은 것 찾기
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (Circle[i][j] == 0)
continue;
if (j == 1) {
if (Circle[i][j] == Circle[i][j + 1]) {
Same.insert(make_pair(i, j));
Same.insert(make_pair(i, j + 1));
}
if (Circle[i][j] == Circle[i][M]) {
Same.insert(make_pair(i, j));
Same.insert(make_pair(i, M));
}
}
else if (j == M) {
if (Circle[i][j] == Circle[i][1]) {
Same.insert(make_pair(i, j));
Same.insert(make_pair(i, 1));
}
if (Circle[i][j] == Circle[i][j - 1]) {
Same.insert(make_pair(i, j));
Same.insert(make_pair(i, j - 1));
}
}
else {
if (Circle[i][j] == Circle[i][j + 1]) {
Same.insert(make_pair(i, j));
Same.insert(make_pair(i, j + 1));
}
if (Circle[i][j] == Circle[i][j - 1]) {
Same.insert(make_pair(i, j));
Same.insert(make_pair(i, j - 1));
}
}
}
}
//다른 원판에서 같은 것 찾기
for (int j = 1; j <= M; j++) {
for (int i = 1; i < N; i++) {
if (Circle[i][j] == 0)
continue;
if (Circle[i][j] == Circle[i + 1][j]) {
Same.insert(make_pair(i, j));
Same.insert(make_pair(i + 1, j));
}
}
}
bool res = false;
//인접하면서 수가 같은 것이 있으면
if (!Same.empty()) {
res = true;
for (auto num : Same) {
Circle[num.first][num.second] = 0;
}
}
//없으면
if(res==false) {
int cnt = 0;
int nsum = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (Circle[i][j] != 0) {
cnt++;
nsum += Circle[i][j];
}
}
}
double Ave = (double)nsum / (double)cnt;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (Circle[i][j] == 0)
continue;
if (Circle[i][j] < Ave)
Circle[i][j]++;
else if (Circle[i][j] > Ave)
Circle[i][j]--;
}
}
}
Same.clear();
}
int main() {
cin >> N >> M >> T;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> Circle[i][j];
}
}
int x, d, k;
while (T--) {
cin >> x >> d >> k;
Turn(x, d, k);
//원판에 수가 없으면
if (findNum() == false) {
cout << 0 << '\n';
return 0;
}
findSame();
}
cout << Sum() << '\n';
return 0;
}'백준 > 시뮬레이션,구현' 카테고리의 다른 글
| (c++)백준 16974번: 레벨 햄버거 (0) | 2021.03.10 |
|---|---|
| (c++)백준 16939번: 2x2x2큐브 (0) | 2021.03.05 |
| (c++)백준 17140번: 이차원 배열과 연산 (0) | 2020.10.17 |
| (c++)백준 17143번: 낚시왕 (0) | 2020.10.17 |
| (c++)백준 16235번: 나무 재테크 (0) | 2020.10.16 |
'백준/시뮬레이션,구현' Related Articles
more
