[Programmers] N으로 표현 - 동적계획법(Dynamic Programming)

// N으로 표현 - 동적계획법(Dynamic Programming) 또는 DFS
public class ExpressionN { // TC가 부족함. N=5, number=26 일 때, 5*5+5/5 => 4 가 리턴되어야 하나 5가 리턴됨
	private int answer = -1;

	public int solution(int N, int number) {
		dfs(N, 0, 0, number);
		return answer;
	}

	private void dfs(int n, int nCount, int via, int number) { // nCount : N을 사용한 개수, via : 지금까지 계산된 값
		if (nCount > 8) // N을 8개 초과사용했을 경우 함수 종료
			return;
		if (via == number) { // number와 같은 값이 됐을 때, nCount의 최소값을 저장
			answer = answer == -1 ? nCount : Math.min(answer, nCount);
			return;
		}
		int nn = 0; 
		for (int i = 1; i <= 8; i++) { // 재귀를 통해 '+', '-', '*', '/' 모두의 경우를 계산
			nn = nn * 10 + n; // ex) n=5 일 때, 5 -> 55 -> 555 ...
			dfs(n, nCount + i, via + nn, number);
			dfs(n, nCount + i, via - nn, number);
			dfs(n, nCount + i, via * nn, number);
			dfs(n, nCount + i, via / nn, number);
		}
	}
}

• DFS로 해결가능(단, TC 통과 못하는 경우 있음...)