글 읽기 - 77%에서 틀린 코드 반례 부탁드려요ㅜㅜ

hongjy910 5년 전 0

처음에 맞았다가 시간을 줄이고 싶어서 고쳐봤는데 어디서 틀렸는지 잘 모르겠습니다.

현재 사다리에서 가로선 추가 후에 현재 사다리나 다음 사다리로 재귀함수 돌리는 방식입니다.

반례 찾을 수 있을까요ㅜㅜ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
	static int n,m,h;
	static int[][] led = new int[31][11];
	static int min;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token = new StringTokenizer(br.readLine());
		n=Integer.parseInt(token.nextToken()); //세로
		m=Integer.parseInt(token.nextToken()); //가로선
		h=Integer.parseInt(token.nextToken()); //가로
		//led = new int[h][n];
		for(int i=1; i<=m; i++) {
			token=new StringTokenizer(br.readLine());
			int a=Integer.parseInt(token.nextToken());
			int b=Integer.parseInt(token.nextToken());
			led[a][b]=1;
		}
		min=h*(n-1);
		for(int i=1; i<n; i++) {
			dfs(0,1,i);
		}	
		if(min>3)
			min=-1;
		System.out.println(min);
	}
	
	private static void dfs(int depth, int r, int cur) {
		if(depth>3)
			return;
		if(min<=depth)
			return;
		if(checkLed()) {
			min=depth;
			return;
		}
		if(cur==n)
			return;
		for (int i = r; i <= h; i++) {
			// 사다리 추가
			if (led[i][cur] == 1 || led[i][cur - 1] == 1 ||led[i][cur + 1] == 1)
				continue;
			led[i][cur] = 1;	
			for(int j=cur; j<=n; j++) {
				if(j!=cur)
					dfs(depth + 1, 1, j);
				else
					dfs(depth + 1, i+1, j);
			}
			led[i][cur] = 0;
		}	
	}
	
	private static boolean checkLed() {
		for(int i=1; i<=n; i++) {
			int r=1;
			int c=i;
			while(r<=h) {
				if(led[r][c-1]!=0) {
					c-=1;
					r++;
					continue;
				}
				if(led[r][c]!=0) {
					c+=1;
					r++;
					continue;
				}
				r++;
			}
			if(i!=c)
				return false;
		}
		return true;
	}
}

hongjy910 5년 전 1

min 초기화 할 때

min = h*(n-1); 가 아닌 min = 4 로 해줬더니 됐습니다 ㅜㅜ

사다리 수가 적을 때 if(min>3) min=-1; 여기서 -1로 셋팅이 안되서 틀린거였습니다... ㅎ...

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

문제

문제

출처

ICPC

77%에서 틀린 코드 반례 부탁드려요ㅜㅜ

hongjy910 5년 전 0

hongjy910 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말