글 읽기 - 15684 사다리 조작 시간 초과 이유를 모르겠습니다

qowhdgn 5년 전 0

이클립스에서 잘 실행되고 테스트케이스는 정상 동작합니다

Scanner 문제인가 해서 인터넷에 여러 사람들이 올린 코드를 보았지만 Scanner로도 시간 초과가 발생하지 않은 것 같더라구요

재귀 형태로 짰는데 너무 많은 반복문이 들어간걸까요?

연산이 불필요하게 많이 된 부분이 있는지 봐 주셨으면 감사하겠습니다 ㅠ

import java.util.Scanner;

public class Main {
	public static int N, H, M, min=4; //최대 3번까지만 선 추가 가능
	public static int arr[][] = new int[31][11];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N= sc.nextInt();
		M = sc.nextInt();
		H = sc.nextInt();
		
		int h, n;
		
		for(int i=0;i<M;i++){
			h=sc.nextInt();
			n=sc.nextInt();
			//오른쪽으로 연결:1 왼쪽으로 연결 -1, 연결x 0 
			arr[h][n] = 1;
			arr[h][n+1] = -1;
		}
				
		sol(0);
		if(min>=4)
			min=-1;
		System.out.println(min);
		
		sc.close();
	}
	
	public static void sol(int added){
		if(min<=3) //값을 찾았으니 더 찾을 필요 없이 return
			return;
        
		if(added>=4){
			return;
		}
		
		boolean flag=false;
		
		flag = chk();
		if(flag==true){
			if(added<min)
				min = added;
			if(min==0)
				return;
		}
		for(int i=1;i<=H;i++){
			for(int j=2;j<=N;j++){
				if(arr[i][j]!=0) // 다리가 연결되어있으면
					continue;			
				if(arr[i][j-1]==0){ //0만 연결 가능
					arr[i][j]=-1; 
					arr[i][j-1]=1; //왼쪽 오른쪽 연결
					
					sol(added+1);
					
					//나오면서 복구
					arr[i][j]=0;
					arr[i][j-1]=0;
				}
				
			}			
		}	
	}
    //사다리로 제대로 갈 수 있는지 확인하는 함수
	public static boolean chk(){
		for(int i=1;i<=N;i++){
			int sum=0, cur=i;
			for(int j=1;j<=H;j++){
				//출발
				if(arr[j][i]==-1) {//왼쪽으로
					//j++;
					i--; //i는 왼쪽
					sum--;
				}
				else if(arr[j][i]==1){//오른쪽
					i++;
					sum++;
				}					
			}
			if(sum!=0) //사다리 타고 제 위치로 돌아왔는지 여부 체크
				return false;
			i=cur; //다음을 위해 i 원상복구
		}	
		return true;		
	}	
}

jh05013 5년 전 0

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

15684 사다리 조작 시간 초과 이유를 모르겠습니다

qowhdgn 5년 전 0

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말