N으로 표현(프로그래머스, Java)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현 | 프로그래머스

알고리즘 설명:

모든 노드의 경우를 확인하여 가장 적은 count 수를 찾기 위해 DFS 탐색방법을 사용하였다.

재귀함수를 이용하여 DFS를 구현하였다.

• 재귀함수로 값을 찾다가 찾는 경우 return으로 돌아가기보다는 전역변수로 answer를 만들어 바로 값을 넣어주고 함수를 return하여 종료해버린다.

• 숫자 사용 개수가 8개가 넘는 경우 (사용 개수는 count로 체크) answer는 -1

• 재귀함수를 돌다가 값을 처음 찾은 경우에는 answer에 count 값을 넣어준다.

• 또 함수에서 값을 찾았지만 다른 재귀함수가 돌다가 더 count 값이 낮은 경우를 찾는 경우에도 count값을 answer에 넣어준다.

• for문으로 숫자 사용 최대 개수만큼 돌려주고 한번 재귀함수를 call 할 때마다 for문이 도는 횟수를 1식 줄인다.(처음 사용되는 숫자가 점점 늘어나기 때문에, ex) 5 -> 7개가 올 수 있음, 55 -> 6개가 올 수 있음)

막혔던 지점:

count가 8일 때는 함수를 호출할 필요없이 그 자체값이 원하는 값과 같은지만 확인하면 됐는데 count값이 8인 경우에도 for문을 돌게 했더니 answer 값이 -1로 고정되었다.

따라서 for문에서 count가 8인경우엔 돌지 않게 수정하여 문제를 해결하였다.

 

package test;


public class PresentationN {
	static int answer = -1;
	
	public static void solution(int n, int number) {
		calc(n,number,0,0);
	}
	public static void calc(int n, int number, int count,int accum) {
		int nn = n;
		
		if(count>8) {
			answer = -1;
			return;
		}
		if(accum==number) {
			if(answer == -1 || answer > count) {
				answer = count;
			}
			return ;
		}
		
		
		for (int i = 1; i < 9-count; i++) {
			
			calc(n,number,count+i,accum+nn);
			
			calc(n,number,count+i,accum-nn);

			calc(n,number,count+i,accum*nn);
	
			calc(n,number,count+i,accum/nn);

			nn = nn*10 + n;
		}

	}


	public static void main(String[] args) {

		int n = 5;
		int number = 12;
		solution(n,number);
		System.out.println(answer);
	}

}