글 읽기 - 질문 게시판 모든 테케 통과하는데 시간초과가 나옵니다..

kimsezin 1년 전 0

이유가 뭘까요..

게시판에 있는 모든 테케는 알맞게 값 나오는것 같습니다..

중간과정도 다 맞았는데 시간초과가 나오네요 배열말고 list로 풀어야할까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B_20056 {

	static int N,M,K;
	static class fireBall
	{
		int x,y;
		int m,d,s;
		public fireBall(int x, int y, int m, int s, int d) {
			super();
			this.x = x;
			this.y = y;
			this.m = m;
			this.d = d;
			this.s = s;
		}
	}
	
	static int dx[]= {-1,-1,0,1,1,1,0,-1}, dy[] = {0,1,1,1,0,-1,-1,-1};
	
	static fireBall map[][][];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken()); //지도크기
		M = Integer.parseInt(st.nextToken()); //파이어볼 개수
		K = Integer.parseInt(st.nextToken()); //이동 횟수

		map = new fireBall[N][N][N*N];
		for(int i=0;i<M;i++)
		{
			st = new StringTokenizer(br.readLine()," ");
			int x = Integer.parseInt(st.nextToken())-1;
			int y = Integer.parseInt(st.nextToken())-1;
			int m = Integer.parseInt(st.nextToken());//질량
			int s = Integer.parseInt(st.nextToken());//속력
			int d = Integer.parseInt(st.nextToken());//방향
			
			int idx=0;
			for(int j=0;j<M;j++)
			{
				if(map[x][y][j]!=null)
					idx++;
				else
					break;
			}
			map[x][y][idx] = new fireBall(x,y,m,s,d);
		}
		
		for(int i=0;i<K;i++)
			solution();
		
		System.out.println(print());
		
	}
	
	private static void solution() { 
		// TODO Auto-generated method stub
		map = move();
		fire();
	}
	
	
	private static fireBall[][][] move() {
		// TODO Auto-generated method stub
		fireBall copy_map[][][] = new fireBall[N][N][N*N];
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++)
			{
				for(int k=0;k<N*N;k++)
				{
					if(map[i][j][k]!=null)
					{
						fireBall temp = map[i][j][k];
						int x = temp.x;
						int y = temp.y;
						int m = temp.m; //질량
						int s = temp.s; //속력
						int d = temp.d; //방향
						
						for(int dir=0;dir<s;dir++)
						{
							x +=dx[d]; //방향으로 속력만큼 이동
							y +=dy[d];
							
							if(x < 0) //위로 초과될시
								x = N-1; //젤 아래로 이동
							if(x > N-1) //젤 아래 초과될시
								x = 0;
							if(y<0)
								y=N-1;
							if(y>N-1)
								y=0;
						}
						
						map[i][j][k]=null; //기존값 없애기
						
						for(int idx=0;idx<M;idx++) // 새로 이동한 자리에 새로운 파이어볼 넣기
						{
							if(copy_map[x][y][idx] == null)
							{
								copy_map[x][y][idx]=new fireBall(x,y,m,s,d);
								break;
							}
						}
					}
				}
			}
		}
		return copy_map;
	}

	static void fire()
	{
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++)
			{
				if(map[i][j][0]!=null)
				{
					int length = 0;
					for(int z=0;z<map[i][j].length;z++)
						if(map[i][j][z]!=null)
							length++;
					if(length>=2)
					{
						int m = 0; //새로만들 파이어볼 질량 합
						int s = 0; //새로만들 파이어볼 속력 합
						int d = map[i][j][0].d; //방향 설정용
						boolean flag = false; //이 전값과 홀,짝값이 다르면 true;
						
						for(int k=0;k<length;k++)
						{
							m += map[i][j][k].m;
							s += map[i][j][k].s;
							if(d%2 != map[i][j][k].d%2)
								flag = true;
						}
						map[i][j] = new fireBall[N*N]; //해당칸에 있던 파이어볼 리셋
						
						m /= 5; //질량 합 / 5
						
						if(m == 0) //0이면 새로 넣지않기
							continue;

						s /= length; //속력 합 / 파이어볼 개수
						
						
						
						int cnt=0;
						
						if(flag == false) //모두 홀,짝 일때
						{
							map[i][j][cnt] = new fireBall(i,j,m,s,0);
							cnt++;
							map[i][j][cnt] = new fireBall(i,j,m,s,2);
							cnt++;
							map[i][j][cnt] = new fireBall(i,j,m,s,4);
							cnt++;
							map[i][j][cnt] = new fireBall(i,j,m,s,6);
						}
						else
						{
							map[i][j][cnt] = new fireBall(i,j,m,s,1);
							cnt++;
							map[i][j][cnt] = new fireBall(i,j,m,s,3);
							cnt++;
							map[i][j][cnt] = new fireBall(i,j,m,s,5);
							cnt++;
							map[i][j][cnt] = new fireBall(i,j,m,s,7);	
						}
					}
				}
			}
		}
	}
	
	static int print()
	{
		int result=0;
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++)
			{
				for(int k=0;k<N*N;k++)
				if(map[i][j][k]!=null)
					result+=map[i][j][k].m;
			
			}
		}
		return result;
	}
}

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

문제

문제

출처

ICPC

질문 게시판 모든 테케 통과하는데 시간초과가 나옵니다..

kimsezin 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말