LEVEL 3 : N으로 표현

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

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

 

• 문제

  • 

    문제

  • N을 사용해서 number을 표현할 수 있는 최소한의 개수를 출력하는 문제

---

풀이

• DFS 를 활용한 문제이다.
• 어떻게 해결해야 될지 몰라 정답 코드를 찾아보았다(아직ㅜㅜ 부족하다)
• 재귀 함수를 활용하여 390,624번을 경우의 수를 코드로 구현
  • 종료 조건 1 : count 값이 8 초과 일 경우 : N이 8번 이상 나온 경우로 이때는 계산할 필요 없으므로 return
  • 종료 조건 2 : 만약 계산한 값이(SUM) 표현해야 할 번호 number와 같다면 그때의 최솟값을 저장하고 retrun
  • x값을 N으로 선언 후 , for문을 통해 1 ~ 8-count를 제외한 만큼 돈다( 8번 이상 나올 수 없으므로)
    • x = N  : dfs(N,number,count+1,sum + x), dfs(N, number, count+1, sum - x), dfs(N, number, count+1, sum * x), dfs(N, number, count+1, sum / x)
    • x = NN : dfs(N,number,count+1,sum + x), dfs(N, number, count+1, sum - x), dfs(N, number, count+1, sum * x), dfs(N, number, count+1, sum / x)
    • ...... 8-count까지 반복
    • N, NN, NN.... 8-count번의 N까지 sum 값에 사칙연산을 실행하여 준다

• public static int answer;
  public static int solution(int N, int number) {
  	answer = Integer.MAX_VALUE;
  	dfs(N,number,0,0);
  	return answer == Integer.MAX_VALUE ? -1 : answer;//dfs로 만족하는 값을 못찾으면 -1, 최솟값 있다면 최솟값 리턴
  }
  private static void dfs(int n, int number, int count, int sum) {
  	if(count > 8)//종료 조건 1
  		return;
  	if(number == sum) {// 종료조건 2
  		answer = Math.min(answer, count);//최솟값 저장
          return;
      }
      int x = n;
    	for(int i=1;i<=8;++i) {//최대 count 값은 8개까지이므로 1~8-count 까지 
        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;// N, NN, NNN , .... , 8-count 개의 N
  	}
  }​

•