글 읽기 - 15684 사다리조작(java) 9% 시간초과 문의드립니다. 주석 작성했습니다.

dkdlrnf0 3년 전 0

혹시 코드상에서 불필요한 처리가 있을까요?

어떠한 부분에서 시간을 단축시켜줘야할까요?

for(int i = 1 ; i <= 3 ; i ++) {
solution(1,1,0,i);
}

24번 라인을 for문으로 바꿔도 9% 시간초과는 발생했습니다.

import java.util.Scanner;

public class Main {
	static int N, M, H;
	static boolean[][] line;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);	
		N = sc.nextInt();
		M = sc.nextInt();
		H = sc.nextInt();
		
		line = new boolean[H + 1][N + 1]; // 사다리 2차원 배열
		
		for(int i = 0; i < M ; i++) {
			line[sc.nextInt()][sc.nextInt()] = true;
		}
		
		// input 
		
		if(search()) { // input을 기준으로 사다리 탐색 후 i == i를 만족할 경우 0 출력 후 종료
			System.out.println(0);
			System.exit(0);
		}else { // i != i 일 경우 재귀(combination) 시작
			solution(1,1,0);
		} // 재귀 모두 종료 후 종료가 안됐을 경우 -1 출력
		System.out.println(-1);
	}
	
	private static void solution(int n, int h, int cnt) {
		// n : 사다리 위치 & h : 사다리 높이 & cnt 사다리 갯수
		if(cnt > 3) return; // 3 초과해서 놓는 경우 return

		if(cnt <= 3) { // 3보다 작은 경우 사다리 탐색하고 i == i 인 경우 종료
			//탐색 하고 강제종료
			if(search()) {
				System.out.println(cnt);
				System.exit(0);
			}
		}
		
		if(n >= N) { // n번째 사다리 index 벗어나는 경우 h(사다리 높이)+1, n(사다리 index) 1로 초기화
			h = h+1;
			n = 1;
		}
		
		if(h > H) return; // h(사다리 높이)가 H를 넘어가면 return
		
		if(!line[h][n]) {
			if((n - 1 == 0 || !line[h][n-1]) && (n + 1 == N || !line[h][n+1])) {
				// 연속된 가로선 조건 처리
				line[h][n] = true;
				solution(n+1, h, cnt+1);
				line[h][n] = false;
			}
		}
		solution(n+1, h, cnt);
		// combination
	}
	
	private static boolean search() {
		for(int i = 1 ; i <= N ; i++) {
			int tmp = i;
			for(int j = 1 ; j <= H ; j++) {
				if(tmp - 1 != 0 && line[j][tmp - 1]) {
					tmp --;
				}else if(tmp != N && line[j][tmp]) {
					tmp++;
				}
			}
			if(tmp != i)
				return false;
		}
		return true;
	}
    
    
    
    
 // -------------------------------------------------
 // 수정 후 ac 코드
    
import java.util.Scanner;

public class Main {
	static int N, M, H;
	static boolean[][] line;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);	
		N = sc.nextInt();
		M = sc.nextInt();
		H = sc.nextInt();
		
		line = new boolean[H + 1][N + 1]; // 사다리 2차원 배열
		
		for(int i = 0; i < M ; i++) {
			line[sc.nextInt()][sc.nextInt()] = true;
		}    
		
		    // input 
		
        if(search()) {
            System.out.println(0);
            System.exit(0);
        }else {
            for(int i = 1 ; i <= 3 ; i ++) {
                solution(1,0,i);
            }
        }
        System.out.println(-1);
    }
	
    private static void solution(int x, int cnt, int max) {
        if(cnt > max) return;
        if(cnt <= max) { 
            if(search()) {
                System.out.println(cnt);
                System.exit(0);
            }
        }

        for(int i = x ; i <= H ; i++) {
            for(int j = 1 ; j < N ; j++) {
                if(line[i][j]) continue;
                if((j - 1 == 0 || !line[i][j-1]) && (j + 1 == N || !line[i][j+1])) {
                    line[i][j] = true;
                    solution(i, cnt+1, max);
                    line[i][j] = false;
                }
            }
        }
    }
	
    private static boolean search() {
        for(int i = 1 ; i <= N ; i++) {
            int tmp = i;
            for(int j = 1 ; j <= H ; j++) {
                if(tmp - 1 != 0 && line[j][tmp - 1]) {
                    tmp --;
                }else if(tmp != N && line[j][tmp]) {
                    tmp++;
                }
            }
            if(tmp != i)
                return false;
        }
        return true;
    }
}

dkdlrnf0 3년 전 0

자답합니다.

combination -> permutation 으로 변경 후 ac 됐습니다.

그정도로 유의미한 차이가 있는건가요?

startlink 3년 전 1

이 문제는 가은 가로선이라고 하더라도 놓는 순서에 따라 다르니 permutation입니다.

dkdlrnf0 3년 전 0

같은 가로선이라고 하더라도 놓는 순서에 따라 다르다는것은

제가 작성한 combination과 동일하게 동작하는거 아닌가요???

qwe910205 2년 전 1

왜 놓는 순서에 따라 다르나요?

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

문제

문제

출처

ICPC

15684 사다리조작(java) 9% 시간초과 문의드립니다. 주석 작성했습니다.

dkdlrnf0 3년 전 0

dkdlrnf0 3년 전 0

startlink 3년 전 1

dkdlrnf0 3년 전 0

qwe910205 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말