20240306_N으로 표현(프로그래머스)

오늘의 TIL은 N으로 표현이라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

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

프로그래머스

 

문제 설명

아래와 같이 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 하시오.

 

 

제한 조건

N은 1 이상 9 이하이다.

number는 1 이상 32,000 이하이다.

수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시한다.

최솟값이 8보다 크면 -1을 return한다.

 

 

해결 방안

동적 계획법(Dynamic Programming)을 사용하여 접근.

N과 number가 같다면 1을 return

N의 사용 횟수가 8을 초과하면 -1을 return -> 최대 시행 횟수가 8회가 되도록 설계

모든 가능한 조합을 고려하면서 중복을 최소화 -> HashSet 사용

조합에 사용할 수 있는 숫자들 N, NN, NNN, ... , NNNNNNNN을

미리 만들어두고 이를 사용하면서 number를 만들 수 있는지 확인.

나눗셈을 하는 경우에는 0이 나오지 않게 주의

 

 

통과한 답안

using System;
using System.Collections.Generic;

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

        List<HashSet<int>> dp = new List<HashSet<int>>();
        for (int i = 0; i <= 8; i ++)
        {
            dp.Add(new HashSet<int>());
        }

        int baseNum = 0;
        for (int i = 1; i <= 8; i++)
        {
            baseNum = 10 * baseNum + N;
            dp[i].Add(baseNum);
        }

        for (int i = 2; i <= 8; i++)
        {
            for (int j = 1; j < i; j++)
            {
                foreach (int a in dp[j])
                {
                    foreach (int b in dp[i - j])
                    {
                        dp[i].Add(a + b);
                        dp[i].Add(a - b);
                        dp[i].Add(a * b);
                        if (b != 0)
                        {
                            dp[i].Add(a / b);
                        }
                    }
                }
            }

            if (dp[i].Contains(number))
            {
                return i;
            }
        }

        return -1;
    }
}

 

 

초기화 및 DP 구현

if (N == number)
{
    return 1;
}

List<HashSet<int>> dp = new List<HashSet<int>>();
for (int i = 0; i <= 8; i ++)
{
    dp.Add(new HashSet<int>());
}

 

우선 처음 생각했던대로 N과 number가 같다면 사용하는 N의 개수는 1개가 되므로 1을 return한다.

 

이후에 각 단계별로 가능한 모든 결과값을 저장하는 dp를 HashSet을 이용하여 만든다.

 

 

BaseNum의 초기화

int baseNum = 0;
for (int i = 1; i <= 8; i++)
{
    baseNum = 10 * baseNum + N;
    dp[i].Add(baseNum);
}

 

N을 사용하는 경우 N을 연결하여 사용하는 NN, NNN을 미리 baseNum으로 초기화한다.

 

 

문제 풀이

for (int i = 2; i <= 8; i++)
{
    for (int j = 1; j < i; j++)
    {
        foreach (int a in dp[j])
        {
            foreach (int b in dp[i - j])
            {
                dp[i].Add(a + b);
                dp[i].Add(a - b);
                dp[i].Add(a * b);
                if (b != 0)
                {
                    dp[i].Add(a / b);
                }
            }
        }
    }

    if (dp[i].Contains(number))
    {
        return i;
    }
}

return -1;

 

N을 2회부터 8회 사용하는 경우에 대해서 두 개의 수를 이용하여 만들 수 있는 조합들을 만들고

해당 조합들을 사용한 N의 개수의 인덱스에 추가한다.

 

이 방법들을 반복하면서 점차 많은 조합수들을 dp에 추가하고,

이 조합수들 중에서 number에 해당하는 수가 있는지 확인하고,

해당하는 수가 있다면 그 인덱스(N을 사용한 횟수)를 return한다.

 

 

오늘은 프로그래머스의 N으로 표현하기 라는 문제를 해결했는데

 

다이나믹 프로그래밍이라고 불리는 개념을 알고리즘 문제에서 사용한다고 들었고,

 

이를 사용하는 문제들을 접했지만 다른 방식으로 문제를 해결했었는데

 

오늘을 기회 삼아 DP를 좀 더 자세히 공부하고 이를 응용하여 문제를 풀이하였다.

 

문제 풀이만으로는 약간 부족한 부분이 느껴져서 이를 좀 더 자세히 정리하는 시간을 가지려고 한다.