[프로그래머스/JAVA] N으로 표현

이 문제는 애초에 동적 계획법이라는 파트 아래에 나와있는 문제였다.
동적 계획법에 대해서는 이전 포스트에 작성해 놓은 것이 있다. 여기서 중요한 것은, 아래의 표 순서에서 1번에 대한 정보는 확인했으니 2번부터 어떻게 절차를 밟아 나갈 것인가에 대한 질문이었다. 

1. 동적 계획법을 사용해서 풀 수 있는 문제인지 확인
2. 문제의 변수 파악
3. 변수 간 관계식 제작(점화식)
4. 메모
5. 기저 상태 파악
6. 구현

또한, 2번부터 6번까지 진행하면서 마지막 구현단계에서 반복문을 사용해서 구현할 것인가, 재귀함수를 사용하여 구현할 것인가에 대한 논의도 이루어져야 했다. 일단 문제는 변수를 파악하고 점화식을 작성하는 것 부터에서 애를 먹었다는 것이다.. 너무 어려워요

그러다가 깊이우선탐색으로 푼 알고리즘이 있어서 그 문제를 연구해봤다. 해당 코드는 이렇다.

import java.util.*;
import java.io.*;
class Solution {
	static int answer = -1;
    
	public static int solution(int N, int number) {
    	dfs(N, number, 0, 0);
    	return answer;
    }
    
    public static void dfs(int N, int number, int count, int sum) {
    	if(count > 8) return;
    	if(number == sum) {
    		if(answer == -1) answer = count;
    		else answer = Math.min(answer, count);
    	}
    	int X = N;
    	for(int i = 1; i <= 8 - count; i++) {
    		dfs(N, number, i + count, sum + X);
    		dfs(N, number, i + count, sum - X);
    		dfs(N, number, i + count, sum * X);
    		dfs(N, number, i + count, sum / X);
    		X = (10 * X) + N;
    	}
    }
}

여기서 깊이 우선 탐색(DFS)은 해당 노드에서 다음 분기로 넘어가기 이전에 해당 노드에 대해 완벽히 파악하고 분기로 넘어가는 것이다. 이렇게 이해하면 쉽다. 미로찾기에서 갈림길이 나왔을 때에 내가 왼쪽을 선택했다면 그 곳에 있는 정보를 다 검색한 후에 다시 갈림길로 돌아와서 오른쪽으로 간다는 것이다.

dfs의 인수로는 N과 number, count와 sum이 있다. 여기서 N과 number의 경우 solution으로 들어오는 파라미터이고, count의 경우 해당 숫자가 몇 개 포함되어 있는지, sum은 현재까지의 합산 값이 몇인지 나타내는 수이다.

처음 dfs(N, number, i + count, sum + X); 이 부분에서 계속 + 수식을 통해 들어가다가, count가 8에서 return하게 되고, sum을 지속적으로 +시킨 값에 -를, 이후에는 *과 /도 실행한다. 즉, 이 방법은 N의 숫자가 8개 까지 쓰이는 곳으로 먼저 깊게 탐색을 하고 7, 6, 5 ... 1 순으로 내려와서 다시 dfs(N, number, i + count, sum - X); 이 방법으로 8부터 1까지 실행하게 되는 방식이다. 모두 끝나게 되면 N를 단순히 사칙연산에서 끝내는 것이 아니라 N을 이어붙인 방식(예를 들어 N이 5라면, 55같은 수를 의미한다.)도 사용하기 때문에 X = (10 * X) + N; 의 문구를 필요로 하며, 반복문을 돌린다.

반복문의 조건이 <= 8 - count인 이유는 count는 N이 몇번 사용되었는지에 대한 판단변수고, 현재 count가 2일 때 즉, 6개 까지 더 사용할 수 있으므로 최대치에서 count를 빼야한다. 이와 같은 방식으로 answer가 최소치일 경우를 알아내어 그 answer값을 return하는 것이 이 문제의 핵심이다.