[JavaScript] 백준 1463번 문제

 

 

 

이 문제는 DP(Dynamic Programming)를 연습하기 좋은 문제입니다.

DP(동적 계획법)에 대한 자세한 설명은 추후에 글을 올리겠습니다.

 

DP에 대해서 간단하게 말씀드리면 

DP는 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용합니다.

 

DP는 재귀와 매우 유사합니다. 하지만, 가장 큰 차이점은

일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 점입니다.

 

 

DP를 사용하기 위한 조건으로는 크게 두 가지가 있습니다.

1. Overlapping Subproblems(겹치는 부분 문제)

• 동일한 작은 문제들이 반복하여 나타나는 경우

2. Optimal Substructure(최적 부분 구조)

• 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우

 

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

let N = Number(input);
let answer = Array.from(Array(N + 1), () => 0);
answer[2] = 1;
answer[3] = 1;

for (let i = 4; i <= N; i++) {
  answer[i] = answer[i - 1] + 1;
  
  if (i % 3 === 0) {
    answer[i] = Math.min(answer[i], answer[i / 3] + 1);
  }
  if (i % 2 === 0) {
    answer[i] = Math.min(answer[i], answer[i / 2] + 1);
  }
}

console.log(answer[N]);

우선은 입력을 받을 코드를 적어줍니다.

answer이라는 이름을 가진 배열을 선언과 동시에 0으로 초기화해줍니다.

 

보통 배열은 0부터 시작을 하지만, 문제풀이의 편의를 위해 N + 1 크기의 배열을 만들고, 1부터 시작하도록합니다.

1은 딱히 건드릴 필요가 없습니다. 1을 만들기 위해서 입니다. 

 

각 인덱스는 연산을 하려는 숫자라고 생각을 하면 됩니다.

예를 들어, answer[2] = 1은 숫자 2는 나누기 2를 하면 1이기 되기 때문에 answer[2]는 값으로 1을 가지게 됩니다.

answer[3] = 1도 같은 이유입니다.

 

이렇게 값을 미리 할당하는 이유는 DP를 사용하기 위한 조건 1에 해당합니다.

인덱스 4부터 값들을 채울 겁니다.

answer[i] = answer[i - 1] + 1; 를 통해서 값들을 모두 생성하고,

아래의 if문을 통해서 DP를 사용하기 위한 조건 2를 처리합니다.

 

이렇게 하면 최소가 되는 경우를 찾을 수 있습니다.