[ 백준 / 17822번 ] Gold III - 원판 돌리기 ( java )
17822번: 원판 돌리기
반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀
www.acmicpc.net
문제
반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다.
- (i, 1)은 (i, 2), (i, M)과 인접하다.
- (i, M)은 (i, M-1), (i, 1)과 인접하다.
- (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
- (1, j)는 (2, j)와 인접하다.
- (N, j)는 (N-1, j)와 인접하다.
- (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)
아래 그림은 N = 3, M = 4인 경우이다.
원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.
다음 그림은 원판을 회전시킨 예시이다.
| 1번 원판을 시계 방향으로 1칸 회전 | 2, 3번 원판을 반시계 방향으로 3칸 회전 | 1, 3번 원판을 시계 방향으로 2칸 회전 |
원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.
- 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
- 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
- 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
- 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.
원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.
입력
첫째 줄에 N, M, T이 주어진다.
둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다.
다음 T개의 줄에 xi, di, ki가 주어진다.
출력
원판을 T번 회전시킨 후 원판에 적힌 수의 합을 출력한다.
풀이
이런 문제를 풀고 있으면 점점 시뮬에 장인이 되어 가는 것을 느낀다.. 시뮬... 시키는 대로만 구현하면 되는 편한 문제.,,
가장 좋은건 시간 초과를 걱정하지 않아도 된다는 점인거 같다...
풀이코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class 원판돌리기 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st =new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int T = Integer.parseInt(st.nextToken());
int[][] arr =new int[N+1][M];
for(int i = 1; i<= N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j<M ; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
for( int t =0; t<T ;t++) {
st = new StringTokenizer(br.readLine());
int X = Integer.parseInt(st.nextToken());
int D = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
if(D==1) {
for(int x = X;x<=N;x+=X) {
for(int k= 0; k<K; k++) {
int a = arr[x][0];
for(int m = 0; m<M-1 ;m++) {
arr[x][m] = arr[x][m+1];
}
arr[x][M-1] = a;
}
}
}else {
for(int x =X; x<=N;x+=X) {
for(int k= 0; k<K; k++) {
int a = arr[x][M-1];
for(int m = M-1; m>0 ;m--) {
arr[x][m] = arr[x][m-1];
}
arr[x][0] = a;
}
}
}
// System.out.println("움직이기");
// for(int i=1; i<=N;i++) {
// for(int j = 0; j<M; j++) {
// System.out.print(arr[i][j]+ " ");
// }
// System.out.println();
// }
boolean flag = false;
int[][] arr2 = new int[N+1][M];
for(int i = 1;i<=N;i++) {
System.arraycopy(arr[i],0,arr2[i],0,M);
}
for(int i=1; i<=N; i++) {
for(int j = 0; j<M;j++) {
int a = arr[i][j];
if(a!=0) {
if(i>1 && arr[i-1][j]==a) {
arr2[i-1][j] =0;
arr2[i][j] =0;
flag = true;
}
if(i<N && arr[i+1][j]==a) {
arr2[i+1][j]=0;
arr2[i][j]=0;
flag = true;
}
if(j>0 && arr[i][j-1]==a) {
arr2[i][j-1] = 0;
arr2[i][j] =0;
flag = true;
}
if(j<M-1 && arr[i][j+1] ==a) {
arr2[i][j+1] = 0;
arr2[i][j] = 0;
flag = true;
}
if(j==0 && arr[i][M-1]==a) {
arr2[i][M-1]= 0;
arr2[i][j] =0;
flag = true;
}
if(j==M-1 && arr[i][0]==a) {
arr2[i][0] = 0;
arr2[i][j] = 0;
flag = true;
}
}
}
}
arr = arr2;
// System.out.println("인접지우기");
// for(int i=1; i<=N;i++) {
// for(int j = 0; j<M; j++) {
// System.out.print(arr[i][j]+ " ");
// }
// System.out.println();
// }
if(!flag) {
int sum =0;
int cnt =0;
for(int i =1; i<=N; i++) {
for(int j =0; j<M;j++) {
sum+=arr[i][j];
if(arr[i][j]!=0)cnt++;
}
}
double mean = 1.0*sum/cnt;
for(int i =1; i<=N; i++) {
for(int j =0; j<M;j++) {
if(arr[i][j]==0)continue;
else if(arr[i][j]<mean)arr[i][j]++;
else if(arr[i][j]>mean)arr[i][j]--;
}
}
// System.out.println("평균쁠마"+mean);
// for(int i=1; i<=N;i++) {
// for(int j = 0; j<M; j++) {
// System.out.print(arr[i][j]+ " ");
// }
// System.out.println();
// }
}
}
int ans = 0;
for(int i =1; i<= N; i++) {
for(int j =0; j<M; j++) {
ans+=arr[i][j];
}
}
System.out.println(ans);
}
}
먼저 여기서 주의해야할 포인트 !
x의 배수 원판을 모두 돌린다. -> 사실 여기서 x+=x 했다가 큰일났었다... 후.. 이런 사소한 실수 안하는 버릇을 길러야 지..
그리고 , 인접한 값들은 모두 사라진다, : 여기서도 처음 코드에서는 arr하나로 쓰다가 이전 값을 위해서 arr2를 선언해서 바꿔준 후에 다시 넣었다.
이 두가지만 주의하면 된다.
먼저 입력 부분이다.
원판을 그냥 int 배열로 저장하고 이를 처음,마지막을 검사하면서 인접을 검사해주도록 하자.
입력부는 아래와 같다.
이제, X, D, K 값에 따라 기존의 원판들을 돌려주도록 한다.
먼저 D값에 따라서 회전하는 방향을 정하고 돌려주도록 한다.
이렇게 짜고
그 안에 X의 배수에 따라 돌릴 수 있도록 함수를 넣어준다.
그리고 다시 그 안에 함수 k 개 만큼 원판이 돌도록 한칸씩 이동시켜준다.
미리 arr[x][0]을 저장해두고, 한칸씩 옮겨주면 반시계 방향으로 돌게 된다.
이렇게 다 돌았으면, 이제 제거하기를 해줘야 한다.
먼저 제거하는 값이 없으면 평균 내서 더하는 작업을 하니까 flag를 하나 설정해서 변한 값이 있는지 없는지 체크해준다.
그리고 이제 인접한 값이 있는지 검사해주면 되늗데,
0인 경우는 검사할 필요가 없고, 같은지 비교를 해주기 위해서 a에 값을 저장해 줬다. 여기서 중요한 점이 arr[i][j]의 값을 저장해주는것이다.
이후 상하좌우, 그리고 원판이었으므로, j가 0일 때와 1일 때까지의 방향을 검사하면서
arr2[i][j]의 값을 바꿔준다. 같을 경우를 말한다. 이렇게 해줘야 중복되서 변하는 값들이 있을 때 문제가 생기지 않는다.
마지막 예제를 통해 이러한 이유를 알 수 있다.
이후 인접한 값들을 지워주면 arr를 바꿔주도록 한다.
그리고 이제 앞에서 사용했던 flag를 다시 이용하는데, 변한 값이 하나도 없으면
값을 모두 더해 평균을 낸 다음 : (여기에서 실수로 검사를 해줘야 하기 때문에, double을 사용한다. )
그리고 기존의 값이 평균보다 크면 1을 빼고,, 작으면 1을 더하고를 반복하면 된다
0인 값은 이미 X가 쳐진 값이라고 생각히므로 continue를 잊으면 안된다. 그리고 평균과 같을 경우는 아무 작없도 하지 않는다.
이렇게 t번의 반복을 하고,
원판에 든 모든 값을 더한 다음 출력해주면
문제는 끝이 다.