[99클럽 코테 스터디 10일차 TIL] 동적계획법

📖 오늘의 학습 키워드
동적계획법

오늘의 회고

문제

[N으로 표현]
https://school.programmers.co.kr/learn/courses/30/lessons/42895

나의 해결

import java.util.*;
class Solution {
    public int solution(int N, int number) {
        Set<Integer>[] set = new HashSet[9];
        for(int i = 1; i < 9; i++) {
            set[i] = new HashSet<Integer>();
            set[i].add(Integer.parseInt(String.valueOf(N).repeat(i)));
            for(int j = 1; j < i; j++) {
                for(int a : set[j]){
                    for(int b : set[i-j]) {
                        set[i].add(a-b);
                        set[i].add(a+b);
                        set[i].add(a*b);
                        if(b != 0) {
                            set[i].add(a/b);
                        }
                    }
                }
            }
            if(set[i].contains(number)){
                return i;
            }
        }
        return -1;
    }
}

1. 각 사용횟수로 만들 수 있는 숫자를 저장할 수 있는 배열을 생성한다.
   • 최솟값이 8보다 크면 -1을 return하므로 배열의 크기는 9로 한다.
   • 횟수마다 같은 계산 결괏값을 중복으로 저장할 필요가 없으므로 HashSet을 사용한다.
2. 1부터 8까지 for 문을 돌며 set[i]를 초기화하고 N을 i번 사용해서 만들 수 있는 숫자를 set[i]에 추가한다.
   • N=5이고 i=3일 때 555가 추가된다.
3. j가 1부터 i까지의 for 문을 돌며 set[j]와 set[i-j]에 저장된 숫자들을 이용해 set[i]에 추가할 숫자를 생성한다.
   • 사칙연산을 수행해서 생성한 결괏값을 set[i]에 추가한다.
   • 나누기를 수행할 때는 나누는 값이 0이 되지 않도록 한다.
4. number가 N을 i번 사용해 만들어져 set[i]에 포함된다면 i 값을 반환한다.
5. 주어진 횟수 안에서 number를 표현할 수 없는 경우 -1을 반환한다.

새로 학습한 내용