본문 바로가기

알고리즘/프로그래머스

N으로 표현

반응형

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

 

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

 

programmers.co.kr


문제 설명

아래와 같이 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 합니다.

입출력 예

Nnumberreturn

N number return
5 12 4
2 11 3

입출력 예 설명

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

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


문제를 처음 봤을 때에는, DFS와 dp를 섞어서(?) 풀면 되겠다 싶었습니다. 일단 N은 고정된 숫자이고 연산 방법이 괄호와 사칙연산만 가능한것을 생각하면, N을 기준으로 해당하는 사칙연산으로 DFS 탐색을 하고, 결과 값이 number와 동일할 경우 해당 count 값을 minimum하게 관리하고, 그리고 count 값이 8보다 클 경우엔 종료 시키도록 하면 될거라고 생각했습니다.

  1. 숫자를 붙이는 경우
  2. 덧셈
  3. 뺄셈
  4. 곱셈
  5. 나눗셈

결국 위의 5가지 케이스로 dfs를 돌리면 될거라고 생각했습니다.
그리고 괄호의 경우도 어떻게 예외 케이스 조건으로 던져야할 지 고민이 많이 되었습니다. 그런데 다른 풀이들을 보면 크게 상관 없이 사용을 하더라구요...

class Solution {
    int answer = 9;
    public int solution(int N, int number) {
        dfs(0, 0, N, number);

        if (answer > 8) {
            return -1;
        }

        return answer;
    }

    void dfs(int value, int count, int N, int number) {
        if (count > 8) {
            return;
        }

        if (value == number) {
            answer = Math.min(answer, count);
            return;
        }

        dfs((value * 10) + N, count + 1, N, number);
        dfs(value + N, count + 1, N, number);
        dfs(value - N, count + 1, N, number);
        dfs(value * N, count + 1, N, number);
        dfs(value / N, count + 1, N, number);
    }
}

처음 제출 했던 코드는 위와 같습니다. 결과는...

테스트 케이스 6, 7, 8번에서 터지더군요..

class Solution {
    int answer = 9;
    public int solution(int N, int number) {
        dfs(0, 0, N, number);

        if (answer > 8) {
            return -1;
        }

        return answer;
    }

    void dfs(int value, int count, int N, int number) {
        if (count > 8) { // 최대 8 조건
            return;
        }

        if (value == number) { // number와 같을 조건 후 최소값 저장
            answer = Math.min(answer, count);
            return;
        }

        int tempN = N;
        for (int i = 0; i < 8 - count; i++) { // N을 N, NN, NNN, NNNN, NNNNN 이렇게 사용한다.
            int tempCount = count + i + 1;
            dfs(value + tempN, tempCount, N, number);
            dfs(value - tempN, tempCount, N, number);
            dfs(value / tempN, tempCount, N, number);
            dfs(value * tempN, tempCount, N, number);

            tempN = (tempN * 10) + N;
        }
    }
}

생각을 해보니 기존에  dfs(value + N, count + 1, N, number);  이렇게 N의 값을 사칙계산 없이 붙여서 사용하는 케이스에 대한 방법을 다음 연산에 이어서 사용하는 케이스를 추가하지 못했던 이유가 있었습니다.

다행히 모든 케이스에 대해서 통과 했으며, 사실 문제 카테고리는 Dynamic Programming이었지만 dfs로 충분히 풀 수 있었습니다. DP로 풀어야 한다면, 아무래도 모든 연산 케이스에 대해 만든 이후에 연산 결과값을 구하고, 앞서 구한 값을 메모지에이션 해서 풀면 되지 않을까 싶기도 합니다...(생각만)

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

정수 삼각형  (1) 2021.10.11