본문 바로가기

문제 풀이/Programmers

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

문제 출처 - Programmers

문제는 여기

 

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

 

programmers.co.kr


[풀이]

1. DFS 탐색을 한다.

2. DFS의 종료 조건은 아래와 같다.

2-1. 현재 탐색의 깊이가 8보다 커진다면 종료

2-2. 현재 값이 구하고자 하는 수와 같다면 최솟값을 비교 후 갱신

3. 반복문을 돌며 자릿수를 늘려간다. (2, 22, 222 이처럼 붙여서 쓸 수도 있기 때문에)

4. 3에서 구해진 값과 현재의 값을 사칙연산을 하며 DFS 탐색을 진행한다.

5. 처음 Max값을 준 min의 값이 그대로라면 8번안에 못 만드는 것이므로 -1을 아니라면 최솟값을 출력한다.

[접근]

1. DP를 사용해 각 숫자를 구하는 데 필요한 최소값을 DP 배열에 담아야겠다고 생각하였으나 생각해야 할 부분이 너무 많아지는 것 같아 DFS로 해결하였다.

[코드]

import java.util.*;

class Solution { 
    static int min = Integer.MAX_VALUE;
    static int num;
    static int n;
    
    public int solution(int N, int number) {
        num = number;
        n = N;
        
        dfs(0, 0);
        
        // 8보다 크면 바로 리턴되므로
        // 최고값인 상태
        if (min == Integer.MAX_VALUE)
            return -1;
        return min;
    }
    
    public void dfs(int depth, int current) {
        // 최소값이 8보다 크면 종료
        if (depth > 8) {
            return;
        }
        
        // 표현해야 하는 숫자와 현재 값이 같으면
        if (num == current) {
            // 현재까지의 깊이와 최소값을 비교해서 갱신
            min = Math.min(depth, min);
            return;
        }
        
        int temp = 0;
            
        for (int i = 0; i < 8; i++) {
            // 깊이 + 자릿수가 8보다 작아야함
            if (depth + i < 8) {
                // 자릿수 늘리기 (2, 22, 222, 2222 이런식으로)
                temp = temp * 10 + n;
                
                // 값을 통해 사칙연산하기
                dfs(depth + i + 1, current + temp);
                dfs(depth + i + 1, current - temp);
                dfs(depth + i + 1, current / temp);
                dfs(depth + i + 1, current * temp);     
            }      
        }
    }
}