[java]원판 돌리기 - 백준17822
문제
풀이
문제 해석을 하자면,
- 주어진 조건을 이행하면서 원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.
풀이
- 여기서는 90도 회전 고정이 아니라서 “반시계는 시계방향 3번” 으로 하면 안된다. -> 시계, 반시계 둘다 구현
- 평균을 int 형태로 하지말고 double 형태로 하라!
- 0을 빈값으로 사용하기 때문에 계산할때 0은 꼭 무시!
- 인접한 수를 구할때는 visited로 방문표시후 한번에 0으로 처리하는것을 권장한다.
- (N,N) 이 아니라 (N,M) 배열 크기라는점! -> (N,N)으로 착각하고 풀다가 한참을 시간낭비 했다 ㅜㅜ
코드
public static int N, M, T;
public static int x, d, k;
public static int[][] inArr = new int[55][55];
public static int[][] xdk = new int[55][3];
public static void rotate() {
int cnt = 1; // 회전수
if(d==0) {
cnt*=k; // 총 이동량
while(cnt-->0) {
for(int i=0; i<N; i++) {
if((i+1)%x != 0) continue; // x 배수 체크
int temp = inArr[i][M-1];
for(int j=M-1; j>0; j--) {
inArr[i][j] = inArr[i][j-1];
}
inArr[i][0] = temp;
}
}
}else { // 반시계
cnt*=k; // 총 이동량
while(cnt-->0) {
for(int i=0; i<N; i++) {
if((i+1)%x != 0) continue; // x 배수 체크
int temp = inArr[i][0];
for(int j=0; j<M-1; j++) {
inArr[i][j] = inArr[i][j+1];
}
inArr[i][M-1] = temp;
}
}
}
}
/*
참고
(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)
*/
public static void deleteNum() {
boolean[][] visited = new boolean[55][55]; // 인접한 수 한번에 제거하기 위해(이게 삑사리 안남)
boolean check = false;
// 가로,세로 비교
for(int i=0; i<N; i++) {
if(inArr[i][0] == inArr[i][M-1]) {
if(inArr[i][0] != 0 && inArr[i][M-1] != 0) check = true;
visited[i][0] = true; visited[i][M-1] = true; //delete
}
for(int j=0; j<M-1; j++) {
if(inArr[i][j] == inArr[i][j+1]) {
if(inArr[i][j] != 0 && inArr[i][j+1] != 0) check = true;
visited[i][j] = true; visited[i][j+1] = true; //delete (가로)
}
}
}
for(int j=0; j<N-1; j++) {
for(int i=0; i<M; i++) {
if(inArr[j][i] == inArr[j+1][i]) {
if(inArr[j][i] != 0 && inArr[j+1][i] != 0) check = true;
visited[j][i] = true; visited[j+1][i] = true; //delete (세로)
}
}
}
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(visited[i][j]) inArr[i][j] = 0; //진짜 delete
}
}
if(check) return; //end
// 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.
double avg =0; int sum = 0; int count = 0;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
sum+=inArr[i][j];
if(inArr[i][j]!=0) count++;
}
}
avg = (double)sum/count;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(inArr[i][j]==0) continue;
if(avg<inArr[i][j]) inArr[i][j]--;
else if(avg>inArr[i][j]) inArr[i][j]++;
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(stk.nextToken());
M = Integer.parseInt(stk.nextToken());
T = Integer.parseInt(stk.nextToken());
for(int i=0; i<N; i++) {
stk = new StringTokenizer(br.readLine(), " ");
for(int j=0; j<M; j++) {
inArr[i][j] = Integer.parseInt(stk.nextToken());
}
}
for(int i=0; i<T; i++) {
stk = new StringTokenizer(br.readLine(), " ");
xdk[i][0] = Integer.parseInt(stk.nextToken());
xdk[i][1] = Integer.parseInt(stk.nextToken());
xdk[i][2] = Integer.parseInt(stk.nextToken());
}
//run
for(int i=0; i<T; i++) {
x = xdk[i][0];
d = xdk[i][1];
k = xdk[i][2];
// 1.회전
rotate();
//debug
// for(int j=0; j<N; j++)
// System.out.println(Arrays.toString(inArr[j]));
// System.out.println(i+"회전 rotate");
// 2.조건에따라 수정 -> 인접하면서 수가 같은 것을 모두 지움
deleteNum();
//debug
// for(int j=0; j<N; j++)
// System.out.println(Arrays.toString(inArr[j]));
// System.out.println(i+"회전 delete");
}
//output
int result=0;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
result+=inArr[i][j];
}
}
System.out.println(result);
}
느낀점
생략
댓글남기기