[Javascript] 백준 1463: 1로 만들기

문제

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

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

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

입력

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

 

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

 

---

 

문제 요약

- 정수 X가 3으로 나누어 떨어지면 3으로 나눈다.

- 정수 X가 2으로 나누어 떨어지면 2로 나눈다.

- 1을 뺀다.

- 위 3개의 연산을 최소한으로 이용해서 1을 만들기

 

풀이 방법

1) 실패한 코드 (시간초과)

- 가능하다면 2보다는 3으로 나누는 것이 빠르게 숫자를 줄일 수 있을 거라 생각

- for문으로 i가 1이 될 때까지 반복하며, 연산 할때마다 count + 1

• 3의 배수이면 3으로 나누기
• 3으로 떨어지지 않을 경우
  • 3의 배수 +1 이면 1 빼고 3으로 나누기 (이 때 1을 빼는 것, 3으로 나누는 것 두번의 연산을 실행하므로 count + 2)
  • 2의 배수이면 2로 나누기
  • 2이면 1 빼기

 

- 시간 초과로 실패했는데, 알고보니 이 문제는 동적계획법(Dinamic Programming)으로 풀어야하는 문제였다.

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

let count = 0;

for (let i = input; i > 0; ) {
  if (i % 3 === 0) {
    i = i / 3;
    count++;
  } else {
    if (i % 3 === 1) {
      i = (i - 1) / 3;
      count += 2;
    }
    if (i % 2 === 0) {
      i = i / 2;
      count++;
    }
    if (i === 2) {
      i = 1;
      count++;
    }
  }
  if (i === 1) {
    break;
  }
}

console.log(count);

 

2) 성공한 코드

- 동적계획법

 

- 이전의 계산한 값을 저장해두기위한 자료구조로서 dp배열을 만든다.

- dp 배열은 n이 1이 되기까지 필요한 최소한의 연산횟수를 저장하는 배열이다.

- 1부터 거슬러 올라가며 숫자 n이 1이 되기까지 몇번의 연산이 필요할지 규칙을 찾아본다.

 

• dp[1] = 0
• dp[2] = dp[1] + 1
• dp[3] = min(dp[2] + 1, dp[1] + 1)
• dp[4] = min(dp[3] + 1, dp[2] + 1)
• dp[5] = dp[4] + 1
• dp[6] = min(dp[5] + 1, dp[3] + 1, dp[2] + 1)

 

규칙을 찾아 정리해보면,

• 2로 나누어 떨어지면, dp[n] = min(dp[n-1] + 1, dp[n/2] + 1)
• 3으로 나누어 떨어지면, dp[n] = min(dp[n-1] + 1, dp[n/3] + 1)
• 2와 3모두로 나누어 떨어지면, dp[n] = min(dp[n-1] + 1, dp[n/2] + 1, dp[n/3] + 1)
• 2와 3모두로 나누어 떨어지지 않으면, dp[n] = dp[n-1] + 1

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

const dp = new Array(input + 1);

dp[1] = 0;
dp[2] = dp[1] + 1;
dp[3] = Math.min(dp[1] + 1, dp[2] + 1);

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

console.log(dp[input]);