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

 

 

---

 

문제

https://www.acmicpc.net/problem/1463

 

 

 

 

실행 결과

 

 

 

 

 

코드(c++)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  // 실행 시간 줄이기
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n;
  cin >> n;

  // 숫자 i를 1로 만드는데 필요한 최소 연산횟수를 저장하는 테이블 선언 및 초기화
  vector<int> dp(n + 1, 0);

  // 첫번째는 연산 필요 없으므로 0으로 설정
  dp[1] = 0;

  for (int i = 2; i <= n; i++) {
    // 1부터 빼고나서 생각
    dp[i] = dp[i - 1] + 1;

    // 2로 나누고 최솟값  비교하여 더 적은 것을 선택
    if (i % 2 == 0) {
      dp[i] = min(dp[i], dp[i / 2] + 1);
    }

    // 3으로 나누고 최솟값 비교하여 더 적은 것을 선택
    if (i % 3 == 0) {
      dp[i] = min(dp[i], dp[i / 3] + 1);
    }
  }

  cout << dp[n];

  return 0;
}

 

 

 

 

코드 설명

 

초기에 잘못 생각했던 부분은 연산의 순서였다.
dp 개념을 몰랐을때는 곧이 곧대로 문제에 나와있는 순서대로 연산을 처리하도록 했다. 

 

하지만 여기서 중요한 것은 최소 연산횟수를 구하는 것이다!
2의 배수, 3의 배수여야만 처리 가능한 첫번째와 두번째 연산과는 달리, 1을 빼는 세번째 연산은 조건이 없다. 

따라서 항상 수행할 수 있는 세번째 연산부터 먼저 고려하고, 그 뒤에 나머지 연산이 필요한지 고려해야한다.

즉, 최소 비용을 고려하기 위한 연산의 우선순위를 따지는 것이 이 문제의 핵심이라고 볼 수 있다.

DP를 이용할 동적 배열 dp를 선언하고 문제를 풀어서 해결했다.

 

 

---