문제풀이)프로그래머스)c#) N으로 표현

N으로 표현

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

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

N으로 숫자를 표현을 해서 사칙연산으로 최소한의 값을 만드는 문제이다.

N 이 예시로 5인경우 

5, 55,555, 5555,55555 등으로도 표현이 가능하다.

사칙연산의 계산 수식에 N이 최소한으로 표현되면서 number(조건)과 같은 최소한의 N의 개수를 리턴하는 문제이다.

 

 DP(Dynamic Programming)과 재귀(Recursion)를 통해서 문제를 해결하는 방식으로 구현을 했으나 역시 테스트 케이스를 정확하게 찾지 못하는 경우가 꽤나 많아서. 완벽하게는 풀지는 못했다.

 

다른 사람의 풀이 코드는 다음과 같다.

  public void cal(int N, int number, int count, int result)
    {
        if (min < count)
            return;
        if (result == number)
        {
            if (count < min)
            {
                min = count;
            }
            return;
        }

        if (count == 8)
        {
            return;
        }
        else
        {
            int rest = 8 - count;
            for (int i = 1; i <= rest; i++)
            {
                int tailmax = i / 2;
                for (int j = 0; j <= tailmax; j++)
                {
                    int head = 0;
                    for (int k = 1; k <= i - j; k++)
                    {
                        head = head * 10 + N;
                    }
                    int next = head;
                    int tail = 0;
                    for (int k = 1; k <= j; k++)
                    {
                        tail = tail * 10 + N;
                    }
                    if (tail > 0)
                        next /= tail;


                    cal(N, number, count + i, result + next);
                    //this.GetValue(eOperationType.PLUS, result, next));
                    cal(N, number, count + i, result - next);
                    cal(N, number, count + i, result * next);
                    cal(N, number, count + i, result / next);
                    cal(N, number, count + i, result * -1 * next);
                    cal(N, number, count + i, result * -1 / next);
                }
                if (i > 2)
                {
                    cal(N, number, count + i, result);
                    cal(N, number, count + i, 0);
                }
            }
        }
    }
    int min = 0;
    public int solution(int N, int number) {
         min = 9; 
         cal(N, number, 0, 0);
          if(min>8)
           min = -1; 
           return min; 
    }

내가 코드로 데이터를 확인해보면서 로그로 찍은 결과는 다음과 같은데

사칙연산에서 곱하기와 나누기는 괄호 연산에 따라 값이 천차만별로 되기 때문에

단순하게 메모이제이션으로 결괏값을 누적하고 사칙연산을 해서 풀이하려고 했던 건 클리어하지 못했다.  너무 시간을 많이 잡아먹어서 다음 기회가 되면 다시 한 번 더 시도해봐야겠다.

 

 ★★★☆☆