[JAVA] N으로 표현 (코딩테스트 고득점 Kit [ 동적계획법(DP)]) - LEVEL3

📂 문제 설명

 

아래와 같이 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

5	12	4
2	11	3

입출력 예 설명

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

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

 

---

📂아이디어 및 알고리즘(문제 풀이)

• N을 최소한으로 사용하여 number를 나타내면 되는 문제이다. 
• N으로 나타내는 방법에는 연산하여 구하는 방법과 N을 중복 사용하여 구할수도 있다.
• 이 문제는 DFS를 이용하여 N의 사용 횟수에 따라 값을 비교해 가며 최솟값을 찾으면 된다.
• DFS에는 사용하고자 하는 n, 사용 갯수를 나타내는 UsingCount, 만들어진 num, 구하고자 하는 number 를 인자로 넣어준다
  • UsingCount가 8보다 크게되면 강제 종료를 시키고
  • num == number이면 UsingCount가 answer보다 작으면 갱신시켜준다.
  • for문에서는 newnum이란 수를 이용하고 i번은 횟 수를 의미하며 N을 몇번 중복 사용하여 연산을 해줄지를 구하여 DFS로 넘겨준다.
  • ex) N=5 이고 i=0일때 5 하나만 이용하여 연산이 가능하고 i=1이면 55로하여 연산이 가능하도록 도와준다.
  • 이런식으로 DFS를 돌며 최솟값을 찾아 줄 수 있게된다.
  • usingCount + (1+i)의 의미는 newnum을 포함시켰을때의 N사용 횟수이다.

📂소스코드

class Solution {
	static int answer= -1;
	
	 public int solution(int N, int number) {
	        
	        DFS(N,0,0,number,"");
	        return answer;
	    }
	 
	 //DFS로 풀기 
	 public static void DFS(int n , int UsingCount, int num, int number, String s) {

		 if(UsingCount > 8) {
			 return;
		 }
		 if(num == number) {
			 if(UsingCount < answer || answer == -1) {
				 answer = UsingCount;
			 }
			 return;
		 }
		 int newnum=0;
         
		 for(int i=0;i<8-UsingCount;i++) {
             		newnum =newnum*10 + n; 
			 DFS(n, UsingCount+1+i, num + newnum, number, s+"+");
			 DFS(n, UsingCount+1+i, num - newnum, number, s+"-");
			 DFS(n, UsingCount+1+i, num * newnum, number, s+"*");
			 DFS(n, UsingCount+1+i, num / newnum, number, s+"/");
		 }
		 
		 
	 }
}

📂후 기 

보기에 간단해 보인 문제인데 막상 풀어보니 어려웠다... 특히 중복사용하여 연산을 해나가야 한다는 아이디어가 떠오르지 않아서 구글링을 하여 참고하여 풀게 되었다. 문제를 직관적으로 보고 최대한 간결하게 생각하여 풀고 싶은데 잘 되지가 않는다ㅠㅠ