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

1. 문제파악

처음으로 풀어보는 DP 문제다. DP는 일정한 규칙을 찾아 점화식을 구하고 문제를 해결하는 방식이라고 들었다.

먼저 무작정 규칙을 찾아볼려고 했지만 전혀 다르게 나왔다. 5로 규칙을 찾았다해도 2로 하면 그새 변하는 식...

그래서 결국 이번엔 인터넷의 힘을 빌렸다 ㅠㅠㅠ..

이 문제는 점화식을 구하는 것 처럼 1부터 규칙을 찾는 문제가 아니다.
5가 1번 쓰일 때 경우의 수, 5가 2번 쓰일 때 경우의 수, ...., 5가 7번까지 쓰이는 경우까지 찾고 number의 경우의 수를 찾는 문제다. 솔직히.. 이게 왜 DP문제인지는 모르겠다.. 근데 DP라고 하니깐 일단 위와같이 풀이해보자.

2. 구현

import java.util.*;
class Solution {
    public int solution(int N, int number) {
        int answer = -1;
        List<HashSet<Integer>> countList = new ArrayList<>();

        //둘이 같다면 1을 리턴
        if (N == number) {
            return 1;
        }

        //해쉬 셋 초기화
        for (int i = 0; i < 9; i++) {
            countList.add(new HashSet<>());
        }

        //1번 사용하는 수는 자기 자신 뿐
        countList.get(1).add(N);


        //1은 이미 했으니 8까지 반복
        for (int i = 2; i < 9; i++) {
            //데이터를 저장할 set
            HashSet<Integer> totalSet = countList.get(i);
            //계산결과가 2가지로 나뉨 (2+2) / 2랑 2 / (2+2)는 다른 수임!
            for (int j = 1; j <= i; j++) {
                //서로 바꿔서도 계산
                HashSet<Integer> postSet = countList.get(i - j);
                HashSet<Integer> preSet = countList.get(j);
                for (int preData : preSet) {
                    for (int postData : postSet) {
                        //사칙연산 실행
                        totalSet.add(preData + postData);
                        totalSet.add(preData - postData);
                        totalSet.add(preData * postData);
                        if (postData != 0) {
                            totalSet.add(preData / postData);
                        }
                    }
                }
            }
            //마지막은 연속된 숫자를 넣어줌
            totalSet.add(Integer.parseInt(String.valueOf(N).repeat(i)));
        }

        //값 찾기
        for (HashSet<Integer> set : countList) {
            if (set.contains(number)) {
                return countList.indexOf(set);
            }
        }
        return answer;
    }
}

중요한 점은 preSet과 postSet을 바꿔서도 계산을 해야하는 점이다.

예를들어 (2+2) / 2와 2 / (2+2)는 다른 값이다. 이를 위해 서로 바꿔서도 계산을 한다.(만약 3이면 (2,1 -> 1,2 -> 3,0))

마지막은 연속된 숫자를 붙여주기 위해 위와 같이 코딩했다.

3. 마무리

DP문제를 처음 풀어봤는데 진짜 머리를 굴려야 겠다는 생각이 든다.

만약 노가다로 DP가 안풀린다면 반드시 다른 방면으로 문제를 해결하도록 해야한다.