백준 1463 자바스크립트

문제

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

접근

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

첫째줄는 1이상 10^6이하의 정수 N이 주어집니다. 수의 범위가 크기 때문에 계산가능한 모든 수를 구하는 완전탐색 등은 이 문제에 어울리지 않은 접근법입니다. 한 번 연산한 값을 기억해 두고 문제를 풀 수 있는 DP가 적절해 보입니다.

 

DP의 인덱스는 숫자를 뜻합니다.

D[N-1]: N에서 1을 빼서 1을 만드는 연산 횟수

D[N/2]: N에서 2를 나눠 1을 만드는 연산 횟수

D[N/3]: N에서 3을 나눠 1을 만드는 연산 횟수

 

D[N]은 숫자 N이 1이 되는데 걸리는 최소한의 연산 횟수를 저장합니다.

N이 2로 나눠진다면 D[N] = D[N-1] + 1 과 D[N/2] + 1 중 더 작은 값, N이 3으로 나눠진다면 D[N] = D[N-1] + 1 과 D[N/3] + 1 중 더 작은 값이 됩니다.

각 경우의 수 뒤에 +1 이 되는 이유는 D[N-1],D[N/2],D[N/3] 이 각 N을 구하기 이전의 연산횟수를 나타내기 때문입니다.

 

예를 한 번 들어볼까요?

D[N-1] + 1 :

4를 1을 빼서 1로 만드는 연산 횟수는 3입니다. 4-1-1-1=1

3을 1을 빼서 1로 만드는 연산 횟수는 2입니다. 3-1-1=1

2를 1을 빼서 1로 만드는 연산 횟수는 1입니다. 2-1=1

이를 뒤집어보면 숫자 N을 1을 만들 때까지 1을 빼는 연산의 횟수는 N-1을 1을 만들 때까지 1을 빼는 연산의 횟수 +1 임을 알 수 있습니다. 

D[N/2] + 1 : 

2를 2로 나눠서 1로 만드는 연산 횟수는 1입니다. 2/2 = 1

4를 2로 나눠서 1로 만드는 연산 횟수는 2입니다. 4/2 = 2, 2/2 =1 

8을 2로 나눠서 1로 만드는 연산 횟수는 3입니다. 8/2 = 4, 4/2 = 2, 2/2 = 1

이를 뒤집어보면 숫자 N을 1을 만들 때까지 2를 나누는 연산의 횟수는 N-1을 1을 만들 때까지 N을 나누는 연산의 횟수 +1 임을 알 수 있습니다.

D[N/3] + 1도 위와 D[N/2] + 1의 경우와 마찬가지입니다.

 

문제를 한 번 풀어볼까요? N=4 로 예를 들어봅시다.

우선 D[0]은 문제 범위 밖이므로 0으로 처리해 줍니다. 

D[1] = 0 입니다. 1을 1로 만들 수 있는 연산의 횟수는 0회이기 때문입니다.

D[4] = Math.min( D[3] + 1 , D[4/2] +1) = Math.min( 1 + 1, 2 + 1 ) = Math.min(2, 3) = 2 가 됩니다.

 

이를 코드로 풀어보면 아래와 같습니다.

풀이

const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map((v) => parseInt(v)));
const solution = (input) => {
  const N = +input;
  const DP = Array.from({ length: N + 1 }, () => 0);

  for (let i = 2; i < N + 1; i++) {
    DP[i] = DP[i - 1] + 1; // 1을 빼서 1로 만드는 연산의 횟수로 우선 설정

    if (i % 2 === 0) {
      // 2로 나눠진다면,
      DP[i] = Math.min(DP[i], DP[i / 2] + 1); // 1을 빼서 1로 만드는 연산의 횟수와  2로 나눠 1로 만드는 횟수 중 더 작은 경우로 선택.
    }

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

  return DP[N];
};

console.log(solution(input)); // 3