글 읽기 - 도저히 모르겠네요...

windy10928 5년 전 0

40 프로 정도에서 틀린다고 나오네요

제가 푼 방식은 dfs를 이용해 먼저 고장나지 않은 버튼들의 조합으로 이동하고자 하는 채널 N 과 차이가 가장 적은 숫자를 구합니다.

그리고 마지막에 아래 두 값을 비교해 최소값을 출력합니다.

구한 숫자를 누른 횟수(자리수) + N과의 차이
최초 채널 100 에서 +,- 버튼만을 이용해 이동한 값

일단 이렇게 풀었는데, 뭐가 틀린지 모르겠네요. 백트래킹이 잘못된건가요.

import java.util.Scanner;

public class Main {
	
	static int N,M;
	static boolean[] broken = new boolean[10];
	static int min;
	static int cnt;
	static int len; 
	static int num = 100;
	
	public static void main (String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();	
		M = sc.nextInt();	 
		len = (N+"").length();	// 이동하려는 채널의 자리수
		
		// 고장난 버튼 체크
		for (int i = 0; i < M; i++) {
			broken[sc.nextInt()] = true;
		}
		
		// 최초 차이 값 저장
		min = Math.abs(N-100);
		
		// 고장나지 않은 숫자 버튼을 가지고 조합
		for (int i = 0; i < 10; i++) {
			if(broken[i]) {
				continue;
			}
			dfs(1,10,i);
		}
		
		// 이동하고자 하는 번호와 가장 가까운 번호 즉, 차이값이 가장 작은 'num'을 찾음. 
		// 번호 입력 후 +,-를 가지고 이동한 경우의 횟수와 최초 100번 채널에서 +,- 만으로 간 경우 횟수를 비교하여 최소값 출력
		System.out.println((num+"").length()+Math.abs(N-num) > Math.abs(N-100) ? Math.abs(N-100): (num+"").length()+Math.abs(N-num));
	}
	
	public static void dfs(int cnt, int w, int sum) {
		// 이동하고자 하는 채널 보다 한자리수 큰 범위까지 탐색
		if(cnt <= len+1) {
			if(min > Math.abs(N-sum)) {	// 차이가 최소값이면,
				min = Math.abs(N-sum);	// 차이를 갱신하고, 조합된 숫자 sum을 저장
				num = sum;
			}
			for (int i = 0; i < 10; i++) {
				if(broken[i]) {
					continue;
				}
				dfs(cnt+1, w * 10, sum + i * w);
			}
		}
		// 백트래킹 
		cnt --;
		sum -= (cnt * w);
	}
	
}

djm03178 5년 전 1

차이의 최솟값이 최적은 아닙니다.

944 7

2 3 4 5 6 7 9

이 경우 888 입력 후 위로 56번 올라간 59회가 정답이지만, 이 코드는 1000을 888보다 먼저 탐색하기 때문에 1000 입력 후 아래로 56번 내려간 60을 출력합니다.

djm03178 5년 전 2

그리고 55~57줄에 백트래킹이라고 하신 부분은 사실 무의미합니다. cnt와 sum은 매개 변수이므로 모두 지역 변수이기 때문에, 재귀호출할 때마다 새로 스택에 만들어지고 함수가 끝날 때마다 없어지는, 즉 매 호출마다 서로 전혀 다른 변수들이기 때문에 이번 호출에서 값을 조정한 것이 이전 호출에서의 값에 아무런 영향을 주지 않기 때문입니다.

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

문제

문제

출처

ICPC

도저히 모르겠네요...

windy10928 5년 전 0

djm03178 5년 전 1

djm03178 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말