99클럽 코테 스터디 18일차 TIL: [프로그래머스] N으로 표현

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

프로그래머스

 

DP를 사용해서 풀 수 있는 문제였다. 

 

처음에는 다음과 같이 만들어진 숫자의 끝에 사칙연산을 추가하는 식으로 풀었다.

• num + N
• num - N
• num * N
• num / N

그런데 이렇게 풀면 오답이다. 만약 5을 4번 사용한다고 했을 때 (5 + 5) * (5 + 5) (= 100)라는 식이 있을 수 있다. 그런데 위 방법대로라면 저 식은 나올 수 없고 (5 + 5) * 5 + 5 (= 55)라는 식만 나올 수 있다. 따라서 위 방법은 모든 경우의 식을 도출할 수 없다. 

 

따라서 만들어진 숫자의 끝에 사칙연산을 추가하는 방법이 아닌, 다음과 같은 방법을 사용해야 한다.

• N을 i개 사용할 경우 나올 수 있는 식은 다음과 같다.
  • N을 1개 사용할 경우 나올 수 있는 식과 N을 i - 1개 사용할 경우 나올 수 있는 식을 사칙연산
  • N을 2개 사용할 경우 나올 수 있는 식과 N을 i - 2개 사용할 경우 나올 수 있는 식을 사칙연산
  • N을 3개 사용할 경우 나올 수 있는 식과 N을 i - 3개 사용할 경우 나올 수 있는 식을 사칙연산
  • ...
  • N을 j개 사용할 경우 나올 수 있는 식과 N을 i - j개 사용할 경우 나올 수 있는 식을 사칙연산

이 방법대로 풀면 된다. 참고로 나눗셈을 할 때는 나누는 수가 0이 되지 않도록 해야 한다.

 

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        
        if (N == number) return 1;
        
        List<Set<Integer>> list = new ArrayList<>();
        // 인덱스 0번째 set
        list.add(new HashSet<>());
        // 인덱스 1번째 set
        Set<Integer> set = new HashSet<>();
        set.add(N);
        list.add(set);
        
        for (int i = 2; i <= 8; i++) {
            set = new HashSet<>();
            
            String str = "";
            for (int j = 0; j < i; j++) {
                str += N;
            }
            set.add(Integer.parseInt(str));
            
            for (int j = 1; j < i; j++) {
                int k = i - j;
                for (int num1 : list.get(j)) {
                    for (int num2 : list.get(k)) {
                        set.add(num1 + num2);
                        set.add(num1 - num2);
                        set.add(num1 * num2);
                        if (num2 != 0) {
                            set.add(num1 / num2);
                        }
                    }
                }
            }
            
            list.add(set);
            
            // N i개로 만든 수
            for (int num : set) {
                if (num == number) return i;
            }
        }
        
        return -1;
    }
}

 

알고리즘은 금방 떠올리는데 사고력이 부족한 거 같다. 좀 더 문제를 살펴보고 삽질을 많이 해보며 생각하는 힘을 길러야겠다..!