BOJ 1463 - 1로 만들기

문제

---

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

문제 분석

---

첫 접근 - 재귀

n이라는 숫자를 1로 만들기까지 필요한 총 연산횟수를 f(n)이라 정의해보자.

문제의 조건에 따라 f(n)이 될 수 있는 케이스는 f(n/3) + 1 , f(n/2) + 1 , f(n-1) + 1 이다.

문제에서는 최소 연산횟수를 찾으라 했으니, 이 세 가지 케이스 중 최소값을 구하면 될 것이다.

아하! 재귀문제로군!

구현도 쉽고, 로직도 간단하다. 이대로 구현해볼까?

보다 효율적인 접근 - DP

하지만 이렇게 풀면 시간초과가 난다. 왜? 입력 숫자의 크기가 최대 10^6이기 때문이다.

이 문제에서는 재귀적인 방식의 단점이 드러난다. 중복되는 연산이 너무 많다는 것.

f(7)의 연산 값은 f(21)에서도, f(14)에서도, f(8)에서도 필요하다.
다시 말해 재귀적인 방식의 풀이에서는 같은 f(7)을 f(21)에서도, f(14)에서도, f(8)에서도 매 번 호출해야 한다는 뜻이다.

이런 경우에는 탑다운 방식의 재귀보다, DP를 활용하는 방식이 좋다. 어딘가에 f(n)의 값을 기억해놓고 있다가, f(n*3),f(n*2),f(n+1)연산 시점에서 추가 연산없이 저장소에서 f(n)값을 꺼내오기만 하면 된다.

구현

---

문제 분석이 끝났다. 어떻게 풀이를 하는 것이 효율적인지도 판단이 섰다. 이제 구현해보자.
1차원 dp 테이블을 이용해서 낮은 숫자부터 높은 숫자까지 순회하며 dp 테이블을 업데이트 시키자.

업데이트 조건은 문제의 조건대로 3으로 나뉘는 경우(가능하다면), 2로 나뉘는 경우(가능하다면), 1을 빼는 경우 이렇게 세가지이다.

n을 3으로 나눈경우의 연산횟수, 2로 나눈경우의 연산횟수, 1을 뺀 경우의 연산횟수 중 최소값에 1을 더한 것이 n을 1로 만들기 위한 최소 연산횟수일 것이다.

테이블로 보면 아래와 같을 것이다.

n	0	1	2	3	4	5	...
f(n)	0	0	1	1	2	3	...

성공한 풀이

---

const N = require('fs').readFileSync(0).toString().trim() * 1

const dp = Array.from({ length: N + 1 }, () => 0)
dp[0] = 1000000 + 1

for (let i = 2; i < N + 1; i++) {
  //case1- 3으로 나누어 떨어지는 경우
  const case1 = i % 3 === 0 ? dp[i / 3] : dp[0]
  //case2 - 2로 나누어 떨어지는 경우
  const case2 = i % 2 === 0 ? dp[i / 2] : dp[0]
  //case3 - 1을 빼는 경우
  const case3 = dp[i - 1]
  dp[i] = Math.min(case1, case2, case3) + 1
}

console.log(dp[N])

회고

백준 단계별 문제풀이 - 동적 계획법1을 풀이 중이다.

재귀적인 방식의 비효율성을 깨닫고, 메모리를 추가로 할당해 시간을 줄이는 방식의 DP는 굉장히 흥미로운 접근법이다.

처음에는 DP적인 사고방식을 갖추지 못해 문제풀이하는데 시간이 많이 걸렸고, 정답 풀이를 보더라도 이런 생각을 어떻게 하지? 라는 생가밖에 안들었었다.

그런데 자꾸 문제를 푸니까 눈이 트이는 느낌이다.

꾸준히 문제를 풀면서 유형탐색을 하자. 어차피 코딩테스트에는 완전히 새로운 문제는 나오지 않는다.