[JAVA] 프로그래머스 - 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 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

---

문제풀이

문제를 보고 DP로 풀어겠다 생각하고 n으로 만들수 있는 최소 숫자를 하나씩 써가면서 규칙을 찾으려 했으나 40분동안 규칙이 전혀 보이지 않았음...

그래서 다른 사람풀이를 보니 n으로 만들수 있는 최소 숫자를 찾는게아니라,

"숫자를 i 개 사용했을때 만들어지는 모든 수들을 하나의 통에 담는다" 는 규칙을 사용한다는걸 알게됨.

 

이에 대해 그림으로 보는게 좋으나... 글로만 간략하게 설명해보겠다.

i번째통 = 숫자 i개를 사용했을때 나오는 모든 값들이 들어가는 통(List<HashSet<Integer>>이용).

숫자 i개로 만들수 있는 값 = 문제에서 주어진 number (N이 아님)

이란걸 알아두고 가자.

 

1번통에 드갈수 있는수 = 숫자 1개로 만들수 있는 값 = N (자기 자신뿐)

2번통에 드갈수 있는수 = 숫자 2개로 만들수 있는 값 = 1번통 (+, -, *, /) 1번통

3번통에 드갈수 있는수 = 숫자 3개로 만들수 있는 값 = 1번통 (+, -, *, /) 2번통, 2번통 (+, -, *, /) 1번통

4번통에 드갈수 있는수 = 숫자 4개로 만들수 있는 값 =

1번통 (+, -, *, /) 3번통, 3번통 (+, -, *, /) 1번통

2번통 (+, -, *, /) 2번통

...

8번통에 드갈수 있는수 = 숫자 8개로 만들수 있는 값 =

1번통 (+, -, *, /) 7번통, 7번통 (+, -, *, /) 1번통 

2번통 (+, -, *, /) 6번통, 6번통 (+, -, *, /) 2번통

3번통 (+, -, *, /)  5번통, 5번통 (+, -, *, /) 3번통

4번통 (+, -, *, /)  4번통

 

이렇게 된다. 8번째 통까지만 하는 이유는 제한사항에 최소값이 8이 넘어가면 어차피 -1을 반환하면 되기때문에

8번통까지만 탐색해주면된다.

 

그리고 참고로 n=8일때 5번째통에는 같은숫자로 이루진수 즉, 사칙연산을 통해 나온수가 아닌 88888 이란 수도 넣어줘야한다는걸 잊지말자.

---

코드

bottom-up

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class Solution {
    public static int solution(int N, int number) {
        //통만들기
    	List<HashSet<Integer>> list=  new ArrayList<HashSet<Integer>>();
        
    	//총 8개 통 만들자~(i는 곧 쓰인 숫자의 개수가됨)
        for(int i=0; i<=8; i++)
        	list.add(new HashSet<Integer>());
        list.get(1).add(N);//숫자 1개만 쓸땐 무조건 자기자신밖에 못드감. 초기화 
        if(number==N) return 1;
        
        //숫자 1개 쓸때는 이미 초기화 했으니 숫자 2개 쓸때부터 탐색 ㄱㄱ
        for(int i=2; i<=8; i++) {
        	//total = 숫자를 i개 썼을때 숫자들이 들어갈 통.
        	HashSet<Integer> total = list.get(i);
        	
        	//이전 통들을 가지고 경우의수 찾기.
        	//예를 들어 3번통에 드갈 숫자들을 찾으려면 
        	//3번통 = 1번통(+,-,*,/)2번통 , 3번통 =  2번통(+,-,*,/)1번통 이됨.
        	for(int j=1; j<i; j++) {
        		HashSet<Integer> a = list.get(j);
        		HashSet<Integer> b = list.get(i-j);
        		
        		//즉, i번째 통 = a(+,-,*,/)b , i번째 통 = b(+,-,*,/)a 
        		for(int x:a) {
        			for(int y:b) {
        				total.add(x+y);
        				total.add(x-y);
        				total.add(x*y);
        				if(x!=0 && y!=0) total.add(x/y);
        			}
        		}
        		//같은숫자로 된거 추가.
        		//예를들어 n=8일때 5번째 통에선 88888 를 넣어줘야함. 
        		total.add(Integer.parseInt(String.valueOf(N).repeat(i)));
        	}
        	
        	//i번째통에 숫자 다채웠을때 통안에 number가 있다면 바로 i번째 통을 반환
        	if(total.contains(number)) return i;
        }
        
        //통 8개를 찾았는데 숫자가 없다? -> 최소값 8이상 -> -1반환
        return -1;
    }
}

---

마치며

DP는 쉬운건 쉬운데,,, 규칙찾기가 좀만 어려워도 난이도가 수직 상승하는 기분임 ㅠ

그리고 이문제를 top-down 방식으로 풀수있는지도 한번 생각해봐야할듯 하다.