DP - 백준 1463

📝 1로 만들기 - 동적 프로그래밍 문제 해결

정수를 1로 만드는 최소 연산 횟수를 구하는 문제 DP로 해결

 

1463 바로가기

 

📌 문제 설명

주어진 정수 X에 대해 다음 세 가지 연산이 가능합니다:

• X가 3으로 나누어 떨어지면, 3으로 나누기
• X가 2로 나누어 떨어지면, 2로 나누기
• 1을 빼기

💡 해결 방법

// 입력 받기
const input = Number(prompt());
const dp = new Array(input + 1).fill(0);

// DP 배열 초기화
dp = 0; // 1은 연산 필요 없음

// Bottom-up 방식으로 최소 연산 횟수 계산
for (let i = 2; i <= input; i++) {
    // 1을 빼는 경우를 기본값으로
    dp[i] = dp[i - 1] + 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);
    }
}

console.log(dp[input]);

🔍 동작 원리

초기 설정

• dp[i]: i를 1로 만드는데 필요한 최소 연산 횟수
• dp = 0으로 초기화 (기저 사례)

각 숫자별 처리

1. 1을 빼는 경우의 연산 횟수 계산
2. 2로 나누어 떨어지는 경우 비교
3. 3으로 나누어 떨어지는 경우 비교
4. 세 가지 경우 중 최솟값 선

⭐️ 예시 실행

N = 10인 경우의 dp 배열 변화:

숫자	최소 연산 횟수	경로
2	1	2→1
3	1	3→1
4	2	4→2→1
5	3	5→4→2→1
10	3	10→9→3→1

 

🚀 시간 복잡도

• O(N): 각 숫자에 대해 한 번씩만 계산
• 공간 복잡도: O(N)의 dp 배열 사용

 

🔍 DP를 적용하면서 궁금하던점

• 왜? 기존 input값보다 크게 넣는가?

  const dp = new Array(input + 1).fill(0);

  
  
  • DP 배열의 인덱스 0은 사용하지 않지만, input 값이 10이 들어왔을때 
    인덱스를 1~10 까지 동일하게 매칭 시키기 위함
•  for 를 통해 i = 2 부터 연산하는 이유?
  • 당연하다. 문제의 의도대로  1은 1이되기까지 최소연산 횟수가 1이기 때문
• for를 통해 i 를 input 값 까지 순회하는 이유?
  • Bottom-up 방식을 통해 1 ~ input 값까지 연산을 구해야지 dp[input] 의 값을 구할 수 있음

dp[2] 계산 → 쉽게 구할 수 있음
dp[3] 계산 → 쉽게 구할 수 있음
dp[4] 계산 → dp[2]의 값을 사용
dp[5] 계산 → dp[4]의 값을 사용
...
dp[10] 계산 → dp[9], dp[5]의 값을 사용