[프로그래머스] N으로 표현 (07.24)

문제

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

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

 

접근법

문제 분류는 DP로 되어있지만 DFS로 해결하였다.

그냥 사칙연산만 있었다면 간단했을텐데 

55, 555처럼 숫자를 이어 붙이는 것까지 가능해서 좀 복잡했다.

tmp라는 변수를 두고 그 변수에 55, 555같이 이어붙여지는 숫자를 넣어주었다.

8개 이상의 숫자는 사용할 수 없으므로 반복문은 8까지만 돌렸다.

 

코드

class Solution {
    private int min = Integer.MAX_VALUE;
    private int N = 0;
    private int number = 0;
    public int solution(int N, int number) {
        this.number = number;
        this.N = N;

        dfs(0,0);

        return min>8? -1:min;
    }

    private void dfs(int num, int cnt){
    	// 숫자가 8개가 넘어가서 return
        if(cnt > 8)
            return;

		// num이 타겟넘버와 같다면 min에 최소값 저장
        if(num == number && cnt <= 8) {
            min = Math.min(cnt, min);
            return;
        }

		//숫자가 이어붙여지는 것을 고려하여 포문을 돌리며 DFS
        int tmp = 0;
        for(int i=1;i<=8;i++){
            tmp = tmp*10 + this.N;
            dfs(num+tmp, cnt+i);
            dfs( num-tmp, cnt+i);
            dfs( num*tmp, cnt+i);
            dfs( num/tmp, cnt+i);
        }
    }
}