👀 문제
https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=kotlin
👊 도전
1. 설계
- 문제 조건에 맞게 진행
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
fun solution(N: Int, number: Int): Int {
val dp = Array<MutableSet<Int>>(9) { mutableSetOf() }
for (i in 1..8) {
if (i == 1) {
dp[i].add(N)
} else {
dp[i].add(N.toString().repeat(i).toInt())
for (j in 1 until i) {
dp[j].forEach { a ->
dp[i - j].forEach { b ->
dp[i].add(a + b)
dp[i].add(a - b)
dp[i].add(a * b)
if (b != 0) dp[i].add(a / b)
}
}
}
}
if (dp[i].contains(number)) {
return i
}
}
return -1
}
}
3. 결과
🤟 성공 🤟
4. 설명
- DP를 이용한다
- 최솟값(N을 사용한 횟수)가 8보다 크면 -1을 리턴하므로 8개를 사용하는 것까지만 확인하면 된다. 따라서 DP의 크기는 8까지를 수용할 수 있도록 9로 설정하였다(index 0은 사용하지 않음).
- i == 1이면 나 자신 N을 넣고, 2 이상이면 i번을 만들기 위한 j를 변수로 추가하여 j, i-j로 만든 수를 사칙연산하여 가능한 숫자를 찾는다
- i는 N을 사용한 횟수를 나타낸다.
- j는 i를 만들기 위해 1부터 시작하는 변수이다. N=5라면 가능한 조합은 dp[1]과 dp[4]를 사칙연산한 값, dp[2], dp[3]을 사칙연산한 값이 된다.
- 따라서 dp[j]의 set와 dp[i-j]의 set를 사칙연산하고 중복을 제거하여 dp[i]에 set 형태로 저장한다.
- cf. N=5로 가능한 사칙연산 값이 dp[4]에서 N을 사칙연산한 값이라고 생각하기 쉬운데, 이 경우는 괄호를 사용한 우선순위 계산을 할 수 없다. (N=5, number=26 케이스를 생각해보면 된다.)