[백준] 1463: 1로 만들기 (javascript)

Link

1463번: 1로 만들기

 

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력 > 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력 >첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

| 예제 입력 1 

2

| 예제 출력 1

1

| 예제 입력 2

10

| 예제 출력 2

3

 

제출

const fs = require("fs");

const input = Number(
  process.platform === "linux" ? fs.readFileSync("/dev/stdin").toString() : `10`
);

const DP = new Array(input + 1).fill(0); // input + 1 개수만큼 0으로 채워진 배열 생성

for (let i = 2; i <= input; 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[input]);

 

풀이과정

이번 문제는 DP(Dynamic Programming, 동적 계획법)을 사용하면 쉽게 풀 수 있다.

 

DP 배열의 인덱스는 1로 만들기 위한 숫자와 동일하다.

예를 들어, 3을 1로 만들 때 연산을 사용하는 횟수의 최솟값은 DP[3]에 저장되어 있을 것이다.

 

이전에 결과값을 재활용하는 DP의 장점을 이용하기 위해서 2부터 입력값까지의 최소 연산 횟수를 DP 배열에 저장한다.

여기서 1은 이미 1이기 때문에 1을 제외한 2부터 for문을 실행해야 한다.

 

DP[i] = DP[i - 1] + 1;

숫자에 사용할 수 있는 연산은 총 세 가지이다.

그 중 1을 빼는 연산을 미리 해서 DP 배열에 저장한다.

이는 숫자를 1로 만드는 과정에서 2나 3으로 나눈 연산과 1을 빼는 연산 중 어느 것이 최소 연산 횟수가 될지 비교하기 위해 저장을 해두는 것이다.

 

예를들어 10에서 1을 빼는 연산을 진행하여 10 - 9 - 3 - 1 의 과정을 거치는 경우,

10의 최소 연산 횟수는 9의 최소 연산 횟수에 1을 더한것과 같다고 볼 수 있다.

 

따라서 위와 같은 식이 성립하게 된다.

 

// 2로 나누어 떨어질 때
if (i % 2 === 0) {
  DP[i] = Math.min(DP[i], DP[i / 2] + 1);
}

// 3으로 나누어 떨어질 때
if (i % 3 === 0) {
  DP[i] = Math.min(DP[i], DP[i / 3] + 1);	
}

해당 숫자가 2나 3으로 나누어 떨어진다면 1을 뺀 연산을 진행한 기존의 DP[i]와 2나 3으로 나눈 숫자의 최소 연산 횟수에 1을 더한 값과 비교하여 최솟값을 DP[i]에 저장한다.

 

여기서 DP[i / 2] 와 DP[i / 3]에 1을 더해주는 이유는 마찬가지로

9의 최소 연산 횟수는 3의 최소 연산 횟수에 1을 더한 값과 같기 때문이다.

 

개념

DP(Dynamic Programming)

• DP의 적용 조건
  • Overlapping Subproblems(겹치는 부분 문제)
  • Optimal Substructure(최적 부분 구조)
• Overlapping Subproblems
  • DP는 문제의 결과값을 재활용해서 전체 답을 구한다.
  • 따라서 동일한 작은 문제가 반복하여 나타날 경우에 사용 가능하다.
• Optimal Substructure
  • 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우에 사용한다.
  • 즉, 특정 문제의 최적 결과가 전체 문제에도 동일하게 적용되어 결과가 변하지 않는 경우에 사용 가능하다.
• DP 예시
  • 피보나치 수열

Math.min()

• 매개변수에 주어진 숫자들 중 가장 작은 값을 반환한다.

 

---

Comment

DP를 처음 접해봐서 어떻게 풀어야 할 지 감이 오지 않았었다.

if - else 문을 사용하기엔 코드가 너무 복잡하고 길어질 것 같아 고민을 했지만 역시나 땡처리..!!

DP에 대한 개념을 찾고, 풀이를 보니 조금은 이해가 된 것 같다😄

아직 나아가야 할 길이 많지만 앞으로도 화이팅 !!

 

LINK

• DP 개념 - 겐지충 프로그래머님의 글
• 백준 풀이 - 나를 제외한 천재들님의 글