[PG] N으로 표현 JAVA

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

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

사용할 숫자 int N, 만들어야하는 숫자 int number 가 주어진다.

N을 사용해 만든 사칙연산 식의 결과가 number이 되도록 할 때 N의 최소 사용횟수를 반환해야한다.

 

1. NN의 형태는 N을 두 번 사용한 것이다. ex : 55 -> 5를 두 번 사용)

2. 최소값이 8보다 클 경우 -1을 반환한다.

 

 

풀이 .

class Solution {
    int answer = -1;

    public void dfs(int cnt, int calc, int N, int number) {
        if(calc == number) {
            if(answer == -1 || answer > cnt) {  // 정답이 한 번도 들어온 적이 없거나 최소값을 갱신한 경우
                answer = cnt;
            }
            return;
        }

        int temp = N;
        for(int i = 1; i <= 8 - cnt; i++) {  // N이 8개까지만 사용되도록 함
            dfs(cnt + i, calc + temp, N, number);
            dfs(cnt + i, calc - temp, N, number);
            dfs(cnt + i, calc * temp, N, number);
            dfs(cnt + i, calc / temp, N, number);

            temp = temp * 10 + N;  // N을 하나 더 붙임
        }
    }

    public int solution(int N, int number) {
        dfs(0, 0, N, number);
        return this.answer;
    }
}

분류는 DP이지만 DFS로 풀었다. 솔직히 어떻게 DP로 풀 수 있는지도 모르겠다.

 

int cnt를 사용해 반복문 내에서 사용할 수 있는 N의 개수를 제한했다.

 

정답 처리는 됐지만 사실 틀린 코드이다.

5*5+5/5 처럼 사칙연산의 규칙에 의해 연산자의 순서보다 *, / 연산자를 먼저 계산하는 경우는 고려할 수 없기 때문이다.

 

문제에 "연산자는 무조건 들어온 순서대로 계산된다." 라는 조건이 있어야만 온전히 정답일 수 있는 코드.