<Lv.3> N으로 표현 (프로그래머스 : C#)

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

📕 문제 설명

n과 number가 주어질 때 n과 사칙연산을 가지고 number를 표현할 때 사용되는 최소의 n개수 반환하기

• Input
  n, number
• Output
  필요한 최소 n개수

예제

풀이

dp[i] = i개를 가지고 만들 수 있는 수

i개의 경우 다음과 같이 구할 수 있다.
ex) N 5개를 가지고 만들 수 있는 수 구하기
(1,4) (2,3) (3,2) (4,1)로 조합 가능
1개를 가지고 만드는 경우와 4개를 가지고 만드는 경우를 순서대로 가능한 케이스들 모두 붙여서 5개를 가지고 만드는 경우를 만들 수 있다. 이걸로 i개를 가지고 만들 수 있는 수에 대한 점화식 세워짐!

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

public class Solution {
    public int solution(int N, int number) {
        if (N == number) return 1; // 같은 경우
        // 초기화
        HashSet<int>[] dp = new HashSet<int>[9];
        for (int i = 0; i < 9; i++)
        {
            dp[i] = new HashSet<int>();
        }
        dp[1].Add(N);
        // 8개까지만 케이스 확인
        for (int i = 2; i <= 8; i++)
        {
            string n = "";
            for (int j = 0; j < i; j++) // N자체 붙여서 만드는 케이스 (ex - 55, 555)
            {
                n += N.ToString();
            }
            dp[i].Add(int.Parse(n));
            
            for (int k = 1; k < i; k++) // 개수 조합 만들기 (ex - 5개한다면 (1,4), (2,3), (3,2), (4,1) 가능)
            {
                List<int> firstDp = dp[i-k].ToList();
                List<int> secondDp = dp[k].ToList();
                
                for (int a = 0; a < firstDp.Count; a++)
                {
                    for (int b = 0; b < secondDp.Count; b++)
                    {
                        dp[i].Add(firstDp[a] + secondDp[b]);
                        dp[i].Add(firstDp[a] - secondDp[b]);
                        dp[i].Add(firstDp[a] * secondDp[b]);
                        if (secondDp[b] != 0) dp[i].Add(firstDp[a] / secondDp[b]);
                    }
                }
            }
            
            if (dp[i].Contains(number)) return i;
        }
        
        return -1;
    }
}

결과