[JS] 백준 1463번 1로 만들기

 

출처

백준 온라인 저지

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

문제

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

 

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

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

 

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.

연산을 사용하는 횟수의 최솟값을 출력하시오.

 

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

풀이

1을 빼거나 2나 3을 나누어 1로 만드는데 걸리는 연산 횟수의 최솟값을 구하는 문제입니다.

 

DP 배열의 index는 숫자를 뜻하고, DP 배열에 계속 연산한 숫자(index)의 최솟값을 집어넣는 방식이라 생각하면 됩니다.

 

DP [N] 값 (숫자)에 값이 바뀌는 경우는 아래와 같습니다.

 

1을 뺀다 : DP[N - 1]

2로 나누어 떨어진다 : DP[N / 2]

3으로 나누어 떨어진다 : DP[N / 3]

 

입력값의 가장 작은 수부터 풀어 나간다 생각하면서, 1을 뺀 값을 우선적으로 구해줍니다.

 

즉 무조건 1을 뺀 해당 숫자를 만들어 주고 2나 3으로 나누어 떨어질 경우의 연산 횟수의 최솟값을 구해야 하기 때문에 아래와 같은 식이 만들어집니다.

 

// 2로 나누어 떨어질 때
DP[N] = Math.min(DP[N - 1] + 1, DP[N / 2] + 1); 

// 3으로 나누어 떨어질 때
DP[N] = Math.min(DP[N - 1] + 1, DP[N / 3] + 1); 

 

만약 DP[N - 1] 값에서 +1을 한 값이 3의 횟수고 DP[N / 3] 의 값은 2의 횟수 일 시 Math.min 메서드로 해당 N값에 최소의 횟수로 바꿔줍니다.

 

매번 필요한 연산을 하지 않고 이전에 연산한 값을 가져와 사용만 하면 된다는 장점인 DP 방식을 이용하는 것입니다.

 

코드

const input = require('fs').readFileSync('/dev/stdin').toString();

const num = Number(input);

const DP = new Array(num + 1).fill(0);

for (let i = 2; i <= num; i++) {
    DP[i] = DP[i - 1] + 1;

    if (i % 2 === 0) {
      DP[i] = Math.min(DP[i], DP[i / 2] + 1);
    }

    if (i % 3 === 0) {
      DP[i] = Math.min(DP[i], DP[i / 3] + 1);	
    }
}

console.log(DP[num]);