[백준] 1463

1로 만들기

풀이

const makeOne = () => {
  let input = parseInt(
    require("fs").readFileSync("/dev/stdin").toString().trim()
  );
  let dp = Array.from({ length: 1000001 }, (n) => 0);

  for (let i = 2; i <= input; i++) {
    dp[i] = dp[i - 1] + 1;
    if (i % 2 === 0) dp[i] = dp[i] < dp[i / 2] + 1 ? dp[i] : dp[i / 2] + 1;
    if (i % 3 === 0) dp[i] = dp[i] < dp[i / 3] + 1 ? dp[i] : dp[i / 3] + 1;
  }
  console.log(dp[input]);
};

makeOne();

반성회

N을 2 or 3으로 나누거나 1을 빼는 연산을 계속 반복하여 1로 만들 때

• 최소 횟수가 보장이 되지 않음
• 조건문이 반복되어 시간복잡도가 늘어남

⇒ 거꾸로 1부터 N까지 도달하는 데에 걸리는 최소횟수를 구한다

1. N의 범위는 1부터 100만까지 ⇒ 길이 1,000,001만큼의 배열 선언 (마지막 인덱스가 100만)

2. 1부터 N까지 모든 자연수에 대해 최소 연산 횟수 계산

   1. i에서 i - 1에 도달하기까지 1을 빼는 연산이 1번 필요하므로 dp[i] = dp[i - 1] + 1

   2. (i가 2의 배수일 경우) i에서 i / 2에 도달하기까지 2로 나누는 연산이 1번 필요하다

      단 i - 1에서 i에 도달했을 때 연산 횟수가 i / 2에서 i에 도달했을 때의 연산 횟수보다 작을 수 있으므로 크기 비교하여 더 작은 횟수를 dp[i]에 저장

   3. (i가 3의 배수일 경우) i에서 i / 3에 도달하기까지 3으로 나누는 연산이 1번 필요하다

      단 i - 1에서 i에 도달했을 때 또는 i / 2에서 i에 도달했을 때 연산 횟수가 i / 3에서 i에 도달했을 때의 연산 횟수보다 작을 수 있으므로 크기 비교하여 더 작은 횟수를 dp[i]에 저장

3. dp[N] 출력