[boj] 1463. 1로 만들기

[boj] 1463. 1로 만들기

• 문제 링크 : https://www.acmicpc.net/problem/1463
• 사용 언어 : Node.js

1463번: 1로 만들기

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

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

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

 

---

 

1. 문제 분석

이번 문제는 주어진 연산을 이용해 1을 만드는 경우의 수중 연산의 횟수가 가장 적은 경우의 연산 횟수를 출력하는 문제입니다.
입력 수의 최소 연산을 구하는 것을 큰 문제라고 하면 해당 수까지 도달하는 과정을 작은 문제로 규정할 수 있는 대표적인 DP 문제입니다
해당 작은 문제들의 풀이 값의 활용을 위해 작은 문제를 풀 때마다 값을 메모리에 저장해 주겠습니다.

 

---

 

2. 솔루션

(1) 재귀 ( 실패 - Stack overflow )

const fs = require('fs')
const input = +fs.readFileSync(process.platform ===
                               'linux' ? '/dev/stdin' : 'input.txt').toString()
                 .trim()

function calculate(value) {
    if (value === 1) return 0;
    let ret = 1 + calculate(value - 1);
    if (value % 3 === 0) {
        const divideByThree = 1 + calculate(value / 3);
        ret = ret > divideByThree ? divideByThree : ret
    }
    if (value % 2 === 0) {
        const divideByTwo = 1 + calculate(value / 2);
        ret = ret > divideByTwo ? divideByTwo : ret
    }
    return ret
}

console.log(caculate(input))

 

(2) Bottom-Up

const fs = require('fs')
const input = +fs.readFileSync(process.platform ===
                               'linux' ? '/dev/stdin' : 'input.txt').toString()
                 .trim()

const memo = [];
memo[1] = 0;

for (let i = 2; i <= input; i++) {
    // 1로 뺀 경우
    memo[i] = 1 + memo[i - 1]
    // 2로 나누어지는 경우 저장 된 값과 최솟값 비교 후 저장
    if (i % 2 === 0 && memo[i] - 1 > memo[i / 2]) {
        memo[i] = 1 + memo[i / 2]
    }
    // 3로 나누어지는 경우 저장 된 값과 최솟값 비교 후 저장
    if (i % 3 === 0 && memo[i] - 1 > memo[i / 3]) {
        memo[i] = 1 + memo[i / 3]
    }
}


console.log(memo[input])

---

마치며

같은 연산들이 반복되며 점진적으로 계산 값이 쌓여 간다는 점에서 DP 유형임을 추론할 수 있는 문제였습니다.