[Programmers 프로그래머스] 42895 N으로 표현 (JAVA)

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

 

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

 

N	number	return
2	11	3
5	12	4

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

DP문제를 해결하기 위해서 DFS를 활용을 했습니다.

먼저 특징으로는 8개를 넘어가면 안되기 때문에 N이 8개가 되면 -1을 리턴하게 했습니다.

그리고 answer 값이 없는 경우에도 -1을 리턴하도록 했습니다.

 

 

class Solution {
    private int answer;
    public int solution(int N, int number) {
		answer = Integer.MAX_VALUE;
		dfs(N, number, 0, 0);
		return answer == Integer.MAX_VALUE ? -1 : answer;
    }
	private void dfs(int n, int number, int cnt, int prev) {
		if (cnt > 8) {	//n의 수가 8개가 넘어가면 -1
			answer = -1;
			return;
		}
		if (prev == number) {	//수식 값이 주어진 number와 같으면 cnt값을 answer에 저장
			answer = Math.min(answer, cnt);
			return;
		}
		int tempN = n;
		for (int i = 0; i < 8 - cnt; i++) {	//사칙연산을 해주고, N의 크기에 따라 cnt를 더해준다.
			int newCount = cnt + i + 1;
			dfs(n, number, newCount, prev + tempN);
			dfs(n, number, newCount, prev - tempN);
			dfs(n, number, newCount, prev / tempN);
			dfs(n, number, newCount, prev * tempN);

			tempN = tempN * 10 + n;
		}
	}
}