문제 설명
자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.
- x에 n을 더합니다
- x에 2를 곱합니다.
- x에 3을 곱합니다.
자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.
제한사항
- 1 ≤ x ≤ y ≤ 1,000,000
- 1 ≤ n < y
내가 푼 풀이
- 모든 경우의 수를 구하는 방식으로 중복을 제거하는 Set 안에 연산한 결과를 전부 넣었다.
- 넣을 수 없는경우 -1을 출력한다.
- dp방법도 있는데 나중에 풀어봐야겠다..
import Foundation
func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
var numSet = Set([x])
var result = 0
while true {
var addSet = Set<Int>()
if numSet.contains(y) {
return result
}
for i in numSet {
if i+n <= y {
addSet.insert(i+n)
}
if i*2 <= y {
addSet.insert(i*2)
}
if i*3 <= y {
addSet.insert(i*3)
}
}
numSet = addSet
result += 1
if numSet.isEmpty {
break
}
}
return -1
}
< DP 풀이>
Array의 크기: y+1, 배열의 원소를 모두 Int의 최댓값으로 선언
시작점 x 의 arr[x] = 0
세가지 연산 x+n , x*2 , x*3 수행후 y보다 같거나 작으면
- x+n <= y : arr[x+n] = min(arr[x]+1, arr[x+n])
- x * 2 <= y : arr[x+n] = min(arr[x]+1, arr[x+n])
- x * 3 <= y : arr[x+n] = min(arr[x]+1, arr[x+n])
최소 연산횟수를 구해야하므로 min 적용한다.
결과: arr[y] : 만약 세가지 연산으로 arr[y] 의 값을 변경하지 못했다면 arr[y] = Int.max
import Foundation
func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
var arr = Array(repeating: Int.max, count: y+1)
arr[x] = 0
for i in x...y where arr[i] != Int.max {
if i+n <= y {
arr[i+n] = min(arr[i] + 1, arr[i+n])
}
if i*2 <= y {
arr[i*2] = min(arr[i] + 1, arr[i*2])
}
if i*3 <= y {
arr[i*3] = min(arr[i] + 1, arr[i*3])
}
}
if arr[y] == Int.max {
return -1
} else {
return arr[y]
}
}'코딩테스트 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 메뉴 리뉴얼 Swift (0) | 2023.04.14 |
|---|---|
| [프로그래머스] 롤케이크 자르기 Swift (0) | 2023.04.14 |
| [프로그래머스] 가장 큰 수 Swift (0) | 2023.04.14 |
| [프로그래머스] 뒤에 있는 큰 수 찾기 Swift (0) | 2023.04.14 |
| [프로그래머스] [1차] 프렌즈4블록 Swift (0) | 2023.04.13 |
