[Swift Algorithm] 1로 만들기BOJ #1463

문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

 

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

입출력 예제

입력

10

출력

3

 

내 문제 풀이

var num = Int(readLine()!)!
var count = 0
var min = num // 최솟값(결괏값) 담을 변수. 아무리 숫자가 커도 주어진 숫자보다 클 수는 없으므로 num 넣고 시작

func solution(_ n: Int, _ count: Int) {
    if count > min { return } // 카운트가 min보다 커지면 어차피 최소가 아니므로 계속할 필요x
    if n == 1 { min = count } // 1일 경우 min 업데이트!
    
    if n % 3 == 0 { solution(n/3, count+1) }
    if n % 2 == 0 { solution(n/2, count+1) }
    solution(n-1, count+1)
}

solution(num, count)
print(min)

👉 DP 문제로, 재귀 호출하면서 1이 될 때마다 최솟값을 확인해주는게 포인트!

• n이 3으로 나눠떨어지는 경우, 2로 나눠떨어지는 경우를 조건으로
  각 연산을 실행하는 재귀 함수를 호출해주었고, 호출마다 카운트했다.
  그리고 -1 연산은 언제든지 가능하므로 조건문 사용하지 않고 호출했다.
• 함수 실행마다 min 값과 count 값을 비교하고,
  count 값이 min보다 클 경우 어차피 해당 연산값은 최소가 아니므로 return 한다.
  반대 경우에는 연산 결괏값이 1이 되었다면 min에 count를 저장해준다.

 

💡 피드백

• DP 공부를 시작하면서 처음 푼 문제였지만, 자체로 어렵지 않았으므로 쉽게 풀었다.
• 아직 DP 알고리즘 문제 풀이의 정확한 포인트나 패턴은 파악하지 못했으므로 많이 풀어봐야겠다.

 

---

문제

https://www.acmicpc.net/problem/1463