프로그래머스 - N으로 표현 (C#)

문제 설명

숫자 N을 이용해서 number를 만드는 방법 중 N의 최소 사용 count를 구하는 문제입니다.
ex) N : 5, number : 12, count = 4 -> (55 + 5) / 5

만약 count가 8보다 크면 -1을 반환합니다.

문제 풀이

N이 1번 사용되는 경우는 N입니다.
N이 2번 사용되는 경우

// count : 2
NN
N + N
N - N
N * N
N / N

N이 3번 사용되는 경우

// count : 3
NNN
N + N + N
N + N - N
N + N * N
N + N / N
NN + N
NN - N
NN * N
NN / N
...

현재 count에서 나올 수 있는 모든 값들을 구하고 그 값들 중 number와 같은 값이 있다면
해당 count를 반환하면 됩니다.

규칙을 보면

ex) count가 1일 때 result { N }

ex) count가 2일 때 result { NN, N + N, N - N, N * N, ...)

ex) count가 3일 때 result { NNN, NN + N, NN - N, NN * N, ...)

count가 2일 때 NN을 추가하고 count 1의 result값에 +, -, x, / 을 추가로 연산한 값을 추가합니다.

count가 3일 때 NNN을 추가하고
count1[i] ( + | - | x | / ) count2[j]를 count3의 result에 추가하고
사칙연산 순서를 고려해서
count2[i] ( + | - | x | / ) count1[j]를 count3의 result에 추가합니다.

count가 4일 때 NNNN을 추가하고
count1[i] ( + | - | x | / ) count3[j]를 count4의 result에 추가하고
count2[i] ( + | - | x | / ) count2[j]를 count4의 result에 추가하고
count3[i] ( + | - | x | / ) count1[j]를 count4의 result에 추가합니다.

제출 코드

using System;
using System.Collections;
using System.Collections.Generic;

public class Solution {
    public int solution(int N, int number) {
        if (N == number) return 1;
        int answer = 0;

        Dictionary<int, List<int>> dp = new Dictionary<int, List<int>>(); // count, result

        dp.Add(1, new List<int>());
        dp[1].Add(N);

        for (int count = 2; count <= 8; count++)
        {
            List<int> result = new List<int>();

            result.Add(GetNNN(N, count));

            for (int i = 1, j = count - 1; i <= count - 1; i++, j--)
            {
                for (int k = 0; k < dp[i].Count; k++)
                {
                    for (int l = 0; l < dp[j].Count; l++)
                    {
                        result.Add(dp[i][k] + dp[j][l]);
                        result.Add(dp[i][k] - dp[j][l]);
                        result.Add(dp[i][k] * dp[j][l]);
                        if (dp[j][l] != 0)
                        {
                            result.Add(dp[i][k] / dp[j][l]);
                        }                        
                    }
                }   
            }            

            if (result.Contains(number))
            {
                answer = count;
                break;
            }
            else
            {
                dp.Add(count, result);
            }
        }

        return answer == 0 ? -1 : answer;
    }

    public int GetNNN(int N, int count)
    {
        string nnn = "";
        for (int i = 0; i < count; i++)
        {
            nnn += N;
        }

        return int.Parse(nnn);
    }

}