글 읽기 - djm03178 님께 질문!!

windy10928 5년 전 0

지난 질문 이렇게 답변 주셨는데요. 백트래킹을 한다면 아래와 같이 코딩하면 될까요?

부족함을 많이 느끼네요 하핫..

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 sum;
	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;
			}
			cnt = 1;
			sum = i;
			dfs(10);
		}
		
		// 이동하고자 하는 번호와 가장 가까운 번호 즉, 차이값이 가장 작은 '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 w) {
		// 이동하고자 하는 채널 보다 한자리수 큰 범위까지 탐색
		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;
				}
				cnt ++;
				sum += (i * w);
				dfs( w * 10);
			}
		}
		// 백트래킹 
		cnt --;
		sum -= (cnt * w);
	}
	
}

djm03178 5년 전 0

헉 물론 그런 식으로 해도 되긴 하지만... 제 말은 그냥 60~62줄을 지우면 그게 그냥 백트래킹이라는 뜻이었는데 오히려 인자로 넘기는 부분을 밖으로 빼셨네요... 재귀호출로 인자를 넘겨주면 나중에 복구하는 과정을 거칠 필요가 없으니까 그대로 두면 된다는 뜻이었습니다. 제대로 동작하는 식이긴 한가요?

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

문제

문제

출처

ICPC

djm03178 님께 질문!!

windy10928 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말