글 읽기 - 예제의 답은 잘나오는데 어디가 문제일까요? 틀린케이스좀 제발 부탁드릴께요

culdm 7년 전 0

잘 진행되다가 5%쯤에서 막히는데 이유가 뭘까요?ㅠㅠ

Q에다가 맵 2차원 배열을 집어넣고

5번을 돌리게되요

1번째 시도에서 4번 그다음꺼에서 4번에서 나오는 맵을 4번 상하좌우로 움직이고

거기서 나오는 맵을 또 4번씩 돌려요

즉, 4번 ,16번 ,16*4번 이런식으로 반복되다가 4의 5승까지 돌리면 멈추고

최고 값을 찾아요...

테스트케이스가 안되는게 뭘까요?ㅠㅠ 제발 도와주세요

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int size;
	static int bestvalue=0;
	public static void main(String...msg){
		Scanner sc = new Scanner(System.in);
		
		size = sc.nextInt();
		int map[][] = new int[size][size];
		for(int i = 0 ; i < size; i++){
			for(int j = 0 ; j < size; j++){
				map[i][j] = sc.nextInt();
			}
		}
		Queue<int[][]> q = new LinkedList<int[][]>();
		
		q.add(map);
	
		for(int i = 0 ; i < 5 ; i++){
			//4방향 반복
			int sz = q.size();
			for(int t = 0 ; t<sz ; t++){
				int nmap[][] = q.poll();
				for(int dir = 1 ; dir<=4; dir++){
					q.add(Execute(nmap,dir));//이것을 큐에넣자
				}
			}
		}
		System.out.println(bestvalue);
	}
	
	public static int[][] Execute(int map[][],int dir){
		int nmap[][] = new int[size][size];
		for(int i= 0; i <size; i++)
			for(int j = 0 ; j <size; j++)
				nmap[i][j] = map[i][j];
		//1위 2아래 3왼 4오
		switch(dir){
			case 1: //위로 몰기때문에 검색한것부터 한칸아래있는것들은 합친다. 
					 // 비었다면 아래것들은 모두 올리고 처리한다 //일단 첫줄 검사 -> 같거나 비었으면 올림 -> 같았을 경우는 올리고 숫자 두배로 뻥 
				for(int y = 0 ; y < size; y++){
					for(int x = 0 ; x < size; x++){
						if(nmap[y][x]==0){
							int cc = 1;
							for(int ty = y; ty<size ;ty++){
								while(ty+cc <size &&nmap[y+cc][x]==0)
									cc++;
								if(ty+cc >= size)
									nmap[ty][x] =0;
								else
									nmap[ty][x] = nmap[ty+cc][x];
							}
						}
						int c=1;
						while(y+c<size && nmap[y+c][x]==0 ){
							c++;
						}
						if(y+c >= size)
							continue;

						if(nmap[y][x]==nmap[y+c][x]){
							nmap[y][x] *=2;
							if(nmap[y][x] > bestvalue)
								bestvalue = nmap[y][x];
							for(int ny = y+1 ; ny<size ; ny++){
								if(ny+c < size){
									while(ny+c < size && nmap[ny+c][x]==0)
										c++;
									if(ny+c >=size)
										nmap[ny][x] = 0;
									else
										nmap[ny][x] = nmap[ny+c][x];
								}else 
								nmap[ny][x] = 0;
							}
						}
					}
				}
				/*for(int y = 0 ;  y< size; y++){
					for(int x = 0 ; x< size; x++){
						System.out.print(nmap[y][x]+" ");
					}
					System.out.println("");
				
				}
				System.out.println("1----------------------");*/
				break;
				case 2:
					for(int y = size-1 ; y >= 0; y--){
						for(int x = 0 ; x < size; x++){
							if(nmap[y][x]==0){
								int cc = 1;
								for(int ty = y; ty>=0 ;ty--){
									while(ty-cc >=0 &&nmap[y-cc][x]==0)
										cc++;
									if(ty-cc <0)
										nmap[ty][x] =0;
									else
										nmap[ty][x] = nmap[ty-cc][x];
								}
							}
							int c=1;
							while( y-c>=0 &&nmap[y-c][x]==0){
								c++;
							}
							if(y-c < 0)
								continue;

							if(nmap[y][x]==nmap[y-c][x]){
								nmap[y][x] *=2;
								if(nmap[y][x] > bestvalue)
									bestvalue = nmap[y][x];
								for(int ny = y-1 ; ny>=0 ; ny--){
									if(ny-c >=0){
										while(ny-c >= 0 && nmap[ny-c][x]==0)
											c++;
										if(ny-c <0)
											nmap[ny][x] = 0;
										else
											nmap[ny][x] = nmap[ny-c][x];
									}else 
									nmap[ny][x] = 0;
								}
							}
						}
					}
				/*	for(int y = 0 ;  y< size; y++){
						for(int x = 0 ; x< size; x++){
							System.out.print(nmap[y][x]+" ");
						}
						System.out.println("");
					}
					System.out.println("2-----------------------");*/
					break;
				case 3:
					for(int x = 0 ; x <size; x++){
						for(int y = 0 ; y < size; y++){
							if(nmap[y][x]==0){
								int cc = 1;
								for(int tx = x; tx<size ;tx++){
									while(x+cc <size &&nmap[y][x+cc]==0)
										cc++;
									if(tx+cc >=size)
										nmap[y][tx] =0;
									else
										nmap[y][tx] = nmap[y][tx+cc];
								}
							}
							int c=1;
							while( x+c <size && nmap[y][x+c]==0){
								c++;
							}
							if(x+c >= size)
								continue;
					

							if(nmap[y][x]==nmap[y][x+c]){
								nmap[y][x] *=2;
								if(nmap[y][x] > bestvalue)
									bestvalue = nmap[y][x];
								for(int nx = x+1 ; nx<size ; nx++){
									if(nx+c <size){
										while(nx+c < size && nmap[y][nx+c]==0)
											c++;
										if(nx+c >=size)
											nmap[y][nx] = 0;
										else
											nmap[y][nx] = nmap[y][nx+c];
									}else 
									nmap[y][nx] = 0;
								}
							}
						}
					}
				/*	for(int y = 0 ;  y< size; y++){
						for(int x = 0 ; x< size; x++){
							System.out.print(nmap[y][x]+" ");
						}
						System.out.println("");
					
					}
					System.out.println("3----------------");*/
					break;
				case 4:
					for(int x = size-1 ; x >=0; x--){
						for(int y = 0 ; y < size; y++){
							if(nmap[y][x]==0){
								int cc = 1;
								for(int tx = x; tx>=0 ;tx--){
									while(x-cc >=0 &&nmap[y][x-cc]==0)
										cc++;
									if(tx-cc <0)
										nmap[y][tx] =0;
									else
								nmap[y][tx] = nmap[y][tx-cc];
								}
							}
							int c=1;
							while( x-c>=0 &&nmap[y][x-c]==0){
								c++;
							}
							if(x-c < 0)
								continue;

							if(nmap[y][x]==nmap[y][x-c]){
								nmap[y][x] *=2;
								if(nmap[y][x] > bestvalue)
									bestvalue = nmap[y][x];
								for(int nx = x-1 ; nx>=0 ; nx--){
									if(nx-c >=0){
										while(nx-c >=0 &&nmap[y][nx-c]==0)
											c++;
										if(nx-c <0)
											nmap[y][nx] = 0;
										else
											nmap[y][nx] = nmap[y][nx-c];
									}else 
									nmap[y][nx] = 0;
								}
							}
						}
					}
			/*		for(int y = 0 ;  y< size; y++){
						for(int x = 0 ; x< size; x++){
							System.out.print(nmap[y][x]+" ");
						}
						System.out.println("");
						
					}System.out.println("4-----------------------");
					*/
					break;
		}
		
		
		return nmap;
	}
}

kepler710 7년 전 1

로직은 이해하지 못했지만

4
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2

케이스의경우 32가 나와야하는데 58번째 줄에서 인덱스에러가 나네요

culdm 7년 전 0

kepler710님

소스 다시 업로드하였는데 한번더 봐주실수 있을까요?ㅠ.ㅠ

kepler710 7년 전 0

죄송합니다..

로직을 이해해서 어느 부분이 잘못됐다고 말씀드리면 좋을텐데

부족한 실력이라 반례밖에 못찾겠네요

2
8 16
16 8

의 경우엔 16이 나와야 맞지만 0이 출력되네요

kepler710 7년 전 1

N=1 인 경우에도 0이 출력되는것으로보아

최대값을 찾는 방법을 수정하면 나아지지않을까 생각합니다.

culdm 7년 전 1

@kepler710님 정말 고맙습니다 ^^ ㅎㅎ

새로이 소스를 짜서 말씀해주신거 다 추가했더니 성공했어요 감사합니다 ^^

kepler710 7년 전 1

다행이네요~~

어제 로직을 이해 못했다고 말씀드렸는데 코드가 난해하다는 뜻은 아니었습니다
원래 남의 코드 이해하는게 가장 어렵다잖아요~~
제 코드를 다시 봐도 어렵더라구요 ㅋㅋㅋ
혹시나 불쾌하게 받아들이셨을수도 있을까봐 걱정했는데 잘 해결됐다니 다행입니다 ㅋㅋ

화이팅 하세용~~

culdm 7년 전 0

@kepler710 아닙니다 ㅎㅎ 감사합니다 ^^ 새로 짜보니 더 눈에 들어올 수 있게 짤 수있더라구요 ㅎㅎ

아래는 새로 짠 코드에요 나중에 평가한번 해주세요

import java.util.*;
public class bb2048 {
	
	static int size;
	static int bestValue = 0;
	public static void main(String...msg){
		Scanner sc = new Scanner(System.in);
		size = sc.nextInt(); //맵 배열의 가로세로 크기
		
		int map[] = new int[size*size];
		
		for(int i = 0 ; i< size*size ; i++){
			map[i] = sc.nextInt();
			if(map[i] > bestValue)
				bestValue = map[i];
		}
		//맵 정보 map [ y * size + x] 
		

		Queue<int[]> q = new LinkedList<int[]>();
		q.add(map);
		
		for(int i = 0 ; i < 5; i++){ //5번 반복
			int Qsize = q.size(); 
			
			for(int r = 0 ; r < Qsize; r++){
				int nmap[] = q.poll(); // 각각의 이동한 정보를 추출
				
				for(int dir = 1 ; dir <= 4; dir++){ //상 하 좌 우 로 실행
					q.add(Execute(nmap,dir));
				}
			}
		}
		System.out.println(bestValue);
		
	}

	public static int[] Execute(int map[], int dir){
		int nmap[] = new int[size*size];
		for(int i = 0 ; i < size*size; i++)
			nmap[i] = map[i];
		
		ArrangeMap(nmap,dir);//정리
		SumMap(nmap,dir); //합치기
		ArrangeMap(nmap,dir); //정리

		return nmap;
	}
	public static void SumMap(int map[],int dir){ //근처의 같은 숫자가 있으면 더한다.
		switch(dir){
			case 1:
				for(int x = 0 ; x < size; x++){
					for(int y = 0 ; y < size ; y++){
						int value = getMap(y,x,map);
						
						if(y+1 >= size) //다음값이 맵을 벗어났다면 continue;
							continue;
						
						if( value == getMap(y+1,x,map)){
							setMap(y,x,value*2,map);
							setMap(y+1,x,0,map);
						
							if(value*2 > bestValue)
								bestValue = value*2;
						}
					}
				}
				break;
			case 2:
				for(int x = 0 ; x < size; x++){
					for(int y = size - 1 ; y > 0 ; y--){
						int value = getMap(y,x,map);
						
						if(y-1 < 0) //다음값이 맵을 벗어났다면 continue;
							continue;
						
						if( value == getMap(y-1,x,map)){
							setMap(y,x,value*2,map);
							setMap(y-1,x,0,map);
							
							if(value*2 > bestValue)
								bestValue = value*2;
						}
					}
				}
				break;
			
			case 3: //좌측
				for(int y = 0 ; y < size; y++){
					for(int x = 0 ; x < size ; x++){
						int value = getMap(y,x,map);
						
						if(x+1 >= size) //다음값이 맵을 벗어났다면 continue;
							continue;
						
						if( value == getMap(y,x+1,map)){
							setMap(y,x,value*2,map);
							setMap(y,x+1,0,map);
							
							if(value*2 > bestValue)
								bestValue = value*2;
						}
					}
				}
				break;
				
			case 4:
				for(int y = 0 ; y < size; y++){
					for(int x = size -1 ; x > 0 ; x--){
						int value = getMap(y,x,map);
						
						if(x - 1 < 0) //다음값이 맵을 벗어났다면 continue;
							continue;
						
						if( value == getMap(y,x-1,map)){
							setMap(y,x,value*2,map);
							setMap(y,x-1,0,map);
							
							if(value*2 > bestValue)
								bestValue = value*2;
						}
					}
				}
				break;
		}
	}
	public static void ArrangeMap(int map[],int dir){ //0이 없게끔 싹 정렬
			Queue<Integer> aq = new LinkedList<Integer>();
			switch(dir){ // 1 상 2 하 3 좌 4 우
				case 1://
					
						for(int x = 0 ; x < size; x++){
							//여기서부터 line정렬
							for(int y = 0 ; y< size; y++){
								int value = getMap(y,x,map); //맵의 정보를 가져옴
									if(value!=0){ //0이 아닌 값을 큐에 저장
										aq.add(value);
									}
							}
							int as = aq.size(); //한 x라인에 있는 y중에 0이 아닌 숫자
							for(int y = 0 ; y < as ; y++){  
								setMap(y,x,aq.poll(),map); // 0을 무시하기위해 가져온 값들을 앞에서부터 배열
							}
							for(int y = as ; y < size; y++)
								setMap(y,x,0,map); // 나머지는 0 으로 처리
							aq.clear();
						}
					break;
				
				case 2:
					for(int x = 0 ; x < size; x++){
						//여기서부터 line정렬
						for(int y = size-1 ; y >= 0; y--){
							int value = getMap(y,x,map); //맵의 정보를 가져옴
								if(value!=0){ //0이 아닌 값을 큐에 저장
									aq.add(value);
								}
						}
						int as = aq.size(); //한 x라인에 있는 y중에 0이 아닌 숫자
						for(int y = size - 1 ; y >= size  - as ; y--){  
							setMap(y,x,aq.poll(),map); // 0을 무시하기위해 가져온 값들을 앞에서부터 배열
						}
						for(int y = size -1 -as  ; y >= 0; y--)
							setMap(y,x,0,map); // 나머지는 0 으로 처리
						
						aq.clear();
					}
					break;
					
				case 3:
					for(int y = 0 ; y < size; y++){
						//여기서부터 line정렬
						for(int x = 0 ; x< size; x++){
							int value = getMap(y,x,map); //맵의 정보를 가져옴
								if(value!=0){ //0이 아닌 값을 큐에 저장
									aq.add(value);
								}
						}
						int as = aq.size(); //한 x라인에 있는 y중에 0이 아닌 숫자
						for(int x = 0 ; x < as ; x++){  
							setMap(y,x,aq.poll(),map); // 0을 무시하기위해 가져온 값들을 앞에서부터 배열
						}
						for(int x = as ; x < size; x++)
							setMap(y,x,0,map); // 나머지는 0 으로 처리
						aq.clear();
					}
					break;
					
				case 4:
					for(int y = 0 ; y < size; y++){
						//여기서부터 line정렬
						for(int x = size - 1 ; x >= 0; x--){
							int value = getMap(y,x,map); //맵의 정보를 가져옴
								if(value!=0){ //0이 아닌 값을 큐에 저장
									aq.add(value);
								}
						}
						int as = aq.size(); //한 x라인에 있는 y중에 0이 아닌 숫자
						for(int x = size - 1 ; x >= size - as ; x--){  
							setMap(y,x,aq.poll(),map); // 0을 무시하기위해 가져온 값들을 앞에서부터 배열
						}
						for(int x = size -1 - as ; x >= 0; x--)
							setMap(y,x,0,map); // 나머지는 0 으로 처리
						
						aq.clear();
					}
					break;
			}
			

	}

	public static int getMap(int y,int x,int map[]){
		return map[y * size + x];
	}
	public static void setMap(int y,int x, int value, int map[]){
		map[ y* size + x ] = value;
	}
}

ckdfuf2001 7년 전 0

혹시 테스트케이스 더 있으시면 알려주실수 있으신가요?

ㅜ 위에것들은 되는데 제출하면 틀렸습니다 나오네요

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

문제

문제

출처

ICPC

예제의 답은 잘나오는데 어디가 문제일까요? 틀린케이스좀 제발 부탁드릴께요

culdm 7년 전 0

kepler710 7년 전 1

culdm 7년 전 0

kepler710 7년 전 0

kepler710 7년 전 1

culdm 7년 전 1

kepler710 7년 전 1

culdm 7년 전 0

ckdfuf2001 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말