글 읽기 - 17406 반례를 못찾겠습니다....

mrseos 4년 전 0

배열돌리기도 잘 되고...

예제도 잘 나오는데 어디가 틀린건지 잘 이해가 안됩니다...

package 백준;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class 배열돌리기 {

	public static int n, r, cnt, min = Integer.MAX_VALUE;
	public static int  N, M, K;
	public static int[] array, data;  
	public static boolean[] check;
	public static int[][] order, arr, cpy;

	public static void phpc(int idx, int count) { //nCr = n-1Cr-1 + n-1Cr
		if(count==r) { //종료조건
			cnt++;
			cpy = new int[N+1][M+1];
			//System.out.println("복사");
			for(int l=0; l<=N; l++) {
				cpy[l] = arr[l].clone();
				//System.out.println(Arrays.toString(cpy[l]));
			}
			//System.out.println();
			//System.out.println("cnt"+cnt);
			for(int i=0; i<n; i++) {
				if(check[i]) {
					int rc = order[array[i]][2];
					for(int j=rc; j>=1; j--) {
						int si = order[array[i]][0]-j;
						int sj = order[array[i]][1]-j;
						rotate(si, sj, j*2+1);
					}
					
					for(int k=1; k<=N; k++) {
						int sum = 0;
						for(int j=1; j<=M;j++) {
							sum = sum + cpy[k][j];
						}
						min = Math.min(sum, min);
					}
					//for(int l=0; l<=N; l++)
						//System.out.println(Arrays.toString(cpy[l]));
					//System.out.println();
					
				}
			}
			return;
		}
		for(int i=0; i<n; i++) { 
			//순열
			if(!check[i]) {
				check[i] = true;
				array[count] = data[i];
				phpc(i, count+1);
				check[i]=false;
			}
		}
	}


	private static void rotate(int si, int sj, int len) {
		//오른쪽
		int t1 = cpy[si][sj+len-1];
		for(int j=sj+len-1; j>=sj+1; j--) {
			cpy[si][j] = cpy[si][j-1];
		}
		// 아래 
		int t2 = cpy[si+len-1][sj+len-1];
		for(int j=si+len-1; j>=si+1; j--) {
			cpy[j][sj+len-1] = cpy[j-1][sj+len-1];
		}
		cpy[si+1][sj+len-1] = t1;
		
		//왼쪽
		int t3 = cpy[si+len-1][sj];
		for(int j=sj; j<sj+len-2; j++) {
			cpy[si+len-1][j] = cpy[si+len-1][j+1];
		}
		cpy[si+len-1][sj+len-2] = t2;
		
		for(int j=si; j<si+len-2; j++ ) {
			cpy[j][sj] = cpy[j+1][sj];
		}
		cpy[si+len-2][sj] = t3;
		
		/*
		for(int l=0; l<=N; l++)
			System.out.println(Arrays.toString(cpy[l]));
		System.out.println();
		*/
	}


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		
		st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		n = r = K;
		arr = new int[N+1][M+1];

		for(int i=1; i<=N;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=1; j<=M;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		order = new int[K+1][3];
		for(int i=1; i<=K; i++) {
			st = new StringTokenizer(br.readLine()," ");
			order[i][0] = Integer.parseInt(st.nextToken());
			order[i][1] = Integer.parseInt(st.nextToken());
			order[i][2] = Integer.parseInt(st.nextToken());
		}
		
		data = new int[K];
		array = new int[K];
		check = new boolean[K];
		for(int i=0; i<K; i++) {
			data[i] = i+1;
		}
		phpc(0, 0);
		System.out.println(min);

	}

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

17406 반례를 못찾겠습니다....

mrseos 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말