[DAY36] JAVA 프로그래머스 N으로 표현

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

프로그래머스

 

N으로 표현 문제는 DP(동적 계획법)으로 해결 할 수 있다. 

DP는 문제의 규칙을 파악하고 점화식을 만드는 것이 가장 중요하다.

 

처음에 문제를 잘못 이해 못해서.. 점화식 만드는게 어려웠다..😢

---

🌘 문제 이해하기 

• 숫자 N 과 만들고자하는 수 number 가 주어진다. 
• N과 사칙연산만 이용해서 number 를 만다는 방법 중 N을 최소한으로 사용한 값을 return
• N은 최대 8번까지 사용 그 이후는 -1로 return

---

🌗 문제 자세히보기

• 숫자를 i 개 사용했을 때 만들어지는 모든 수들을 하나의 set에 담는 것이다. 
• 숫자가 최대 8번까지 사용 가능하므로 숫자는 8개 , 즉 8개의 set이 만들어 진다. 

HashSet<Integer>[] dp = new HashSet[9];
   
//최대 8회 
for(int i=1;i<=8;i++)
{
    dp[i] = new HashSet<>();              
}

 

• dp[1] , 숫자를 1번만 사용한 것은 자기자신 N 이 끝 N 과 number 이 동일하면 1 return
• dp[2] 부터는 앞에 있는 dp[1]의 값으로 사칙연산을 만들어서 dp[2] 에 담는다. 
• dp[i]에는 i이전의 통에 담긴 값들로 사칙연산을 만들어서 만들수 있는 수들을 구한다.

for(int i=2;i<9;i++)
{
    for(int j=1;j<i;j++)
    {
        for(int x : dp[j]) //기준값
        {
            for(int y : dp[i-j]) //비교값(기준값의 앞에 값) 
            {
                //숫자 i개를 사용하였을때 만들어지는 모든 수를 하나의 set에 담아라
                //사칙연산       
                dp[i].add(x+y);  //더하기
                dp[i].add(x-y);  //빼기
                dp[i].add(x*y);  //곱하기
                if(y!=0)
                    dp[i].add(x/y); //나누기(나머지 무시)
            }                   
        }

        //i자리 수 추가 
        dp[i].add(Integer.parseInt(String.valueOf(N).repeat(i)));
    }

---

 

🌕 최종 코드 

    public static int solution(int N, int number) {

        if(N == number)
            return 1;


        HashSet<Integer>[] dp = new HashSet[9];
   
        //최대 8회 
        for(int i=1;i<=8;i++)
        {
            dp[i] = new HashSet<>();              
        }

        dp[1].add(N); 

        for(int i=2;i<9;i++)
        {
            for(int j=1;j<i;j++)
            {
                for(int x : dp[j]) //기준값
                {
                    for(int y : dp[i-j]) //비교값(기준값의 앞에 값) 
                    {
                        //숫자 i개를 사용하였을때 만들어지는 모든 수를 하나의 set에 담아라
                        //사칙연산       
                        dp[i].add(x+y);  //더하기
                        dp[i].add(x-y);  //빼기
                        dp[i].add(x*y);  //곱하기
                        if(y!=0)
                            dp[i].add(x/y); //나누기(나머지 무시)
                    }                   
                }

                //i자리 수 추가 
                dp[i].add(Integer.parseInt(String.valueOf(N).repeat(i)));
            }

            if(dp[i].contains(number))
                return i; //최소값
           
        }

        return -1;
    }
}