[프로그래머스 C#] Lv.3 N으로 표현

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 N과 사칙연산만으로 number를 표현할 때, N의 최소 개수를 구하는 문제

- N은 9개이상 사용할 수 없으며, 만약 만들 수 없다면 -1을 반환해야 함

 

2차원 배열 List<HashSet<int>> ints 를 선언

- N의 개수로 만들 수 있는 모든 수를 HashSet에 넣음

 ex) ints[i] : i개의 N으로 만들 수 있는 수들

 

모든 수를 넣기 위해선 연산된 수 간의 연산도 처리해주어야 함

- 코드 상에서 i = index1+ index2 를 만족시켜야 하는 이유가 됨

 + 중복 연산을 최소화 하기 위해 index1 >= index2 인 경우에만 연산함

 

i = 2 : 1 1
i = 3 : 1 2  
i = 4 : 1 3 / 2 2
i = 5 : 1 4 / 2 3
i = 6 : 1 5 / 2 4 / 3 3
i = 7 : 1 6 / 2 5 / 3 4
i = 8 : 1 7 / 2 6 / 3 5 / 4 4

 

https://godgjwnsgur7.tistory.com/109

[Algorithm C#] 동적 계획법(DP) / Memoization, Tabulation

 

주석 참조

    using System;
    using System.Collections.Generic;

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

            var ints = new List<HashSet<int>>(); // 2차원 배열
            ints.Add(new HashSet<int>()); // 인덱스 번호를 맞추기 위함

            // i : N의 개수
            for (int i = 1; i <= 8; i++)
            {
                // ints[i] : N을 i개 사용해 나올 수 있는 수
                ints.Add(new HashSet<int>()); 

                // 이어붙인 숫자 세팅
                int total = N;
                for (int j = 1; j < i; j++)
                    total += N * (int)Math.Pow(10, j);
                ints[i].Add(total);

                // i = index1 + index2가 언제나 만족하도록 세팅
                int index1 = 1;
                int index2 = i - 1;

                // N이 i개 있는 연산으로 나올 수 있는 수 세팅
                while (index1 <= index2)
                {
                    foreach (int num1 in ints[index1])
                        foreach (int num2 in ints[index2])
                            Function(ints[i], num1, num2);

                    index1++; index2--;
                }

                // 만약 위 연산 과정에서 0이 생겼다면 지워줌
                ints[i].Remove(0);

                // 목표 번호를 만드는데 성공했을 경우
                if (ints[i].Contains(number))
                    return i;
            }

            return -1;
        }

        // num1과 num2의 사칙연산으로 나올 수 있는 모든 결과를 hs에 넣는 메서드
        public void Function(HashSet<int> hs, int num1, int num2)
        {
            // 음수가 들어가지 않도록
            if (num1 > num2) hs.Add(num1 - num2);
            if (num2 > num1) hs.Add(num2 - num1);

            hs.Add(num1 * num2);
            hs.Add(num1 + num2);
            hs.Add(num1 / num2);
            hs.Add(num2 / num1);
        }
    }