https://www.acmicpc.net/problem/12100
2048이지만 좀쉬운버전..
중간에 숫자가 안생기고 합쳤을때 최고수가 나올경우를 하면된다
조건도 5번 주어져있기때문에
결국 상 하 좌 우
4^5 번 즉 1024개의 조합수가 나오고 해당 조합수만큼 돌려주고 Max값을 ㅐㅈ주면끝
물론..이제 move 하는 과정이 중요하다..
나는 여기서 한가지 실수를 해서 오래걸렸는데
메소드에서
public void a (int [][] array)로 되어있다면 저 array를 가지고 넘겨주고 넘겨주고 하면 제대로된값이 작동이안된다.. 즉.. clone 혹은 2중포문 복사를해야된다..
나같은경우에는 array를 넣어주면 그냥 새로 뿅 생기는줄알고 기존에 생각해왔는데 해당 array의 주소값을 넘겨주고 작업하는
방식이기때문에.. 다시한번.. 제대로 알고넘어가기로한다..
move 의 핵심 아이디어는 다음과 같이 정리하였다..
이렇게 민다고 진행하면
이렇게 접근할 순서를 먼저 선택해준다..
그러면 하나의 얘로 1만 본다고 가정하면 위로밀기때문에 2번값과 3번값을 신경쓸 필요가없으니 1번값만 보도록한다..
만약 값이 있는 경우와 없는경우를 보면
이렇게 체크를 해주면된다..
- 값이 있는경우
한칸 한칸 이동하면서 다음값의 존재여부를 확인하고 값이있따면 조건을 확인
합쳐져있는 경우를 boolean으로 체크하고 합쳐진 적이있으면 그냥 당겨주기
합쳐진 경험이 없는 경우 값이 일치하면 * 2 아니면 그냥 거기서 종료
- 값이 없는경우
그냥 옮겨줌
그러면 요렇게된다
그리고 아까 2번 3번을 똑같이 진행해주면 끝
이게 위로 당기기의 로직이다. 아래로 당길때는 반대로하면되고
위아래의 로직을 완성했다면
왼쪽 오른쪽은 어떻게하느냐
다음 그림을보자
사실상 위아래를 만들었으면 i와 j값을 포지션을 교체해주면 그게 왼쪽 오른쪽이다
근데..필자는..좀식이더럽다 ㅎㅎ;; 중간에 중복적인부분을 그냥 하드코딩 떄렷다 ㅎㅎ;;
메인로직 (2가지 방법 순서의차이)
- 조합수 다구하기
- 해당 조합에 해당하는만큼 move
- 큰값찾기
or
- 한번 상하좌우 한값을 구하기
- 그값을 매개변수 넘겨줘서 진행하기
- 5번진행했을떄 큰값찾기
아무래도 전자가 좀 깔끔해서 전자의 방법을 하기로했다..
import java.util.*;
import java.io.*;
public class 이공사팔2 {
static int N;
static int answer;
static boolean[][] combc;
static int[] dir;
public static void main(String[] args) throws Exception{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[][] array;
dir = new int[5];
array = new int[N][N];
StringTokenizer st;
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
int cur = Integer.parseInt(st.nextToken());
array[i][j] = cur;
}
}
answer =-1;
// move(array,0);
array = movearray(array,3);
System.out.println(answer);
}
public static void move(int[][] array, int count) {
if(count==5) {
// answer = Math.max(arraymax(array),answer);
int[][] temp = new int[N][N];
for(int a=0;a<N;a++) {
for(int b=0;b<N;b++) {
temp[a][b] = array[a][b];
}
}
temp = movearray(temp,dir[0]);
temp = movearray(temp,dir[1]);
temp = movearray(temp,dir[2]);
temp = movearray(temp,dir[3]);
temp = movearray(temp,dir[4]);
answer = Math.max(arraymax(temp),answer);
return ;
}
for(int i=0;i<4;i++) {
dir[count] = i;
move(array,count+1);
}
}
public static int[][] movearray(int[][] array, int dir){
combc = new boolean[N][N];
if(dir==0) { //위로 당기기
for(int i=0;i<N;i++) { //y의 좌표
for(int j=1;j<N;j++) { //x 의 좌표부터 당겨주기
int cur = array[j][i];
if(cur==0) continue;
boolean exist = false;
for(int k=j-1;k>=0;k--) { // 해당 좌표부터 위로 당겻을때 검사해주기
if(array[k][i]!=0) { // 앞에 검사하는데 합칠수있을경우만 체크
if(array[k][i]==cur && !combc[k][i]) {
exist = true;
}
break;
}
// 검사한 원소의 자리가 비어있지않고 동일하며 합쳐진 기록이없다면 그곳으로 합쳐서 당겨오기
}
if(!exist) { //해당 좌표를 당겼을때 합쳐질수없다면 빈곳중에 남는자리로 당겨오기
for(int k=0;k<=j;k++) {
if(array[k][i]==0) {
array[k][i]=cur;
array[j][i]=0;
break;
}
}
}
else { //합치기가능한경우 합쳐주기
for(int k=j-1;k>=0;k--) {
if(array[k][i]!=0) {
combc[k][i] = true;
array[k][i]+=cur;
array[j][i] = 0;
break;
}
}
}
}
}
}
else if(dir==1) { //아래로당겨주기
for(int i=0;i<N;i++) { //y의 좌표
for(int j=N-2;j>=0;j--) { //x 의 좌표부터 당겨주기
int cur = array[j][i];
if(cur==0) continue;
boolean exist = false;
for(int k=j+1;k<N;k++) { // 해당 좌표부터 위로 당겻을때 검사해주기
if(array[k][i]!=0) { // 앞에 검사하는데 합칠수있을경우만 체크
if(array[k][i]==cur && !combc[k][i]) {
exist = true;
}
break;
}
// 검사한 원소의 자리가 비어있지않고 동일하며 합쳐진 기록이없다면 그곳으로 합쳐서 당겨오기
}
if(!exist) { //해당 좌표를 당겼을때 합쳐질수없다면 빈곳중에 남는자리로 당겨오기
for(int k=N-1;k>=j;k--) {
if(array[k][i]==0) {
array[k][i]=cur;
array[j][i]=0;
break;
}
}
}
else { //합치기가능한경우 합쳐주기
for(int k=j+1;k<N;k++) {
if(array[k][i]!=0) {
combc[k][i] = true;
array[k][i]+=cur;
array[j][i] = 0;
break;
}
}
}
}
}
}
else if(dir==2) { //오른쪽
for(int i=0;i<N;i++) { //x의 좌표
for(int j=N-2;j>=0;j--) { //y 의 좌표부터 당겨주기
int cur = array[i][j];
if(cur==0) continue;
boolean exist = false;
for(int k=j+1;k<N;k++) { // 해당 좌표부터 당겻을때 검사해주기
if(array[i][k]!=0) { // 앞에 검사하는데 합칠수있을경우만 체크
if(array[i][k]==cur && !combc[i][k]) {
exist = true;
}
break;
}
// 검사한 원소의 자리가 비어있지않고 동일하며 합쳐진 기록이없다면 그곳으로 합쳐서 당겨오기
}
if(!exist) { //해당 좌표를 당겼을때 합쳐질수없다면 빈곳중에 남는자리로 당겨오기
for(int k=N-1;k>=j;k--) {
if(array[i][k]==0) {
array[i][k]=cur;
array[i][j]=0;
break;
}
}
}
else { //합치기가능한경우 합쳐주기
for(int k=j+1;k<N;k++) {
if(array[i][k]!=0) {
combc[i][k] = true;
array[i][k]+=cur;
array[i][j] = 0;
break;
}
}
}
}
}
}
else { //왼쪽
for(int i=0;i<N;i++) { //x의 좌표
for(int j=1;j<N;j++) { //y 의 좌표부터 당겨주기
int cur = array[i][j];
if(cur==0) continue;
boolean exist = false;
for(int k=j-1;k>=0;k--) { // 해당 좌표부터 위로 당겻을때 검사해주기
if(array[i][k]!=0) { // 앞에 검사하는데 합칠수있을경우만 체크
if(array[i][k]==cur && !combc[i][k]) {
exist = true;
}
break;
}
// 검사한 원소의 자리가 비어있지않고 동일하며 합쳐진 기록이없다면 그곳으로 합쳐서 당겨오기
}
if(!exist) { //해당 좌표를 당겼을때 합쳐질수없다면 빈곳중에 남는자리로 당겨오기
for(int k=0;k<=j;k++) {
if(array[i][k]==0) {
array[i][k]=cur;
array[i][j]=0;
break;
}
}
}
else { //합치기가능한경우 합쳐주기
for(int k=j-1;k>=0;k--) {
if(array[i][k]!=0) {
combc[i][k] = true;
array[i][k]+=cur;
array[i][j] = 0;
break;
}
}
}
}
}
}
return array;
}
public static int arraymax(int[][] array) {
int max=-1;
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(array[i][j]>max) max= array[i][j];
}
}
return max;
}
}
중복적인 부분은..지우면되지만..너무귀찮아서.. 무지성 복사붙이기를했다..
많이틀린이유는 ㅠㅠ .. array 이동에 관련된 실수로인해.. 메인로직은 냅두고 해당부분을 수정하니까..답이나왔다 ㅎㅎ..
골2도 돌파했으니.. 이제 분할정복으로 넘어가자
노력하는 뚠뚠이