(C#) N으로 표현

코딩테스트 연습 - N으로 표현 | 프로그래머스 스쿨

프로그래머스

 딱 보자마자 풀이가 떠오르지는 않는 문제였다. 오히려 감조차 잡을수 없었다.

 

 혼자 고민 해서는 풀지 못할듯 하여 검색해보았다.

 핵심 아이디어는 동적 프로그래밍을 사용하는데, dp[i]에는 N을 i번 사용해서 만들 수 있는 숫자들을 기록하는 것이었다.

 지금까지의 동적 프로그래밍에서는 dp[i]에 하나의 값만 기록했었는데, 이렇게 데이터셋을 기록하는 방식이 새로웠다.

 

 dp에 들어갈 자료구조는 HashSet을 사용했다. HashSet은 javascript의 Set와 같은 자료구조로, 중복값을 허용하지 않는다.

 

HashSet<T> 클래스 (System.Collections.Generic) | Microsoft Learn

HashSet<T> 클래스 (System.Collections.Generic)

 

  dp를 만든 뒤에는 dp를 채워야한다.

 기본적으로 dp[i]에 N을 i+1번 연속으로 사용한 숫자를 채워준다.

dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]
5	55	555	5555	55555	555555	5555555	55555555	555555555

 그리고 i = 0 부터 i = 8 까지 순회하며 dp[i]를 채워넣는다.

 

 예를들어 i = 3일 때, dp[3]은 dp[0]과 dp[2]를 사칙연산 한 값 + dp[1]과 dp[1]을 사칙연산 한 값이 될 것이다.

 즉, dp[i] = dp[0] △ dp[i-1] ∪ dp[1] △ dp[i-2] ∪ ... ∪ dp[j] △ dp[i - j - 1]  ∪  ... ∪ dp[i-1] △ dp[0] 이고,

 이는 j = 0부터 j = i-1까지 dp[j] & dp[i - j - 1] 의 합집합이다.

 (a△b는 a와 b를 사칙연산(+, -, *, /)한 결과의 집합. 즉, {a+b, a-b, a*b, a/b})

 

 이렇게 dp[i]를 채워나가다가, dp[i]에 number값이 들어가게 되면 i+1을 반환하고 종료한다.

 

코드

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int N, int number)
    {
        int answer = -1;
        HashSet<int>[] dp = new HashSet<int>[9];
        for (var i = 0; i < 9; i++)
        {
            dp[i] = new HashSet<int>();
            dp[i].Add(foo(N, i));
        }

        for (var i = 0; i < 9; i++)
        {
            for (var j = 0; j < i; j++)
            {
                foreach (var u in dp[j])
                {
                    foreach (var v in dp[i - j - 1])
                    {
                        dp[i].Add(u + v);
                        dp[i].Add(u - v);
                        dp[i].Add(u * v);
                        if (v != 0 && u % v == 0) // 나누어 떨어질때만 추가
                            dp[i].Add(u / v);
                    }
                }
            }
            if (dp[i].Contains(number)) return i + 1;
        }
        return answer;
    }

    int foo(int N, int count)
    {
        if (count == 0)
        {
            return N;
        }
        return 10 * foo(N, count - 1) + N;
    }
}