[DP 문제풀이] - 1로 만들기

1로 만들기 문제

• 정수 X가 주어졌을 때 , 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지다.

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

• 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 값을 1로 만들고자 한다.
• 연산을 사용하는 횟수의 최솟값을 출력하여라.
• 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.
• 26 → 25 → 5 → 1

• 다이나믹 프로그래밍 문제르 해결할 때는 점화식을 세우는것이 가장 중요하다.

• 이것을 위해 각 항을 어떻게 정의할 수 있는지가 중요하다.

• f(x) = x번째 항 = x까지 보았을 때 최적의 해(문제에서 요구하는 바)
  [정의] f(x): x를 1로 만들기 위해 필요한 연산의 최소 개수

• f(x)을 구하기 위해서 인접한 항들을 이용할 수 있는가?

• 다이나믹 프로그래밍을 해결할 때는, 경험적으로 시도해보는 것도 좋은 방법이다.
  → 일단 시도하다 보면 점화식이 보이는 경우가 종종 있다.

• f(1) = 0 (이유: 이미 값이 1임.)

• f(2) = 1 (이유: 1 빼거나 2로 나눌 수 있음.)

• f(3) = 1 (이유: 3으로 나눌 수 있음.)

• f(4) = 2 (이유: 1을 뺀뒤 f(3), f(2)나눌 수 있음.)

• f(5) = 1 (이유: 5로 나눌 수 있음.)

• f(6) = 2 (이유: 1을 뺀뒤 f(5), 2를 빼고 f(3), 3을 빼고 f(2))

f(x) : x를 1로 만들기 위한 최소 연산 횟수 f(12) : min(f(11)), f(4), f(6)**+1 ** (1번의 연산을 사용)

• 결과적으로 점화식을 세울 수 있다.
• 현재의 예시에서 +1 항은 하나의 연산을 사용하는 행위로 이해할 수 있다.

f(i) = min(f(i - 1), f(i/2), f(i/3), f(i/5)) +1

// 정수 x 입력받기

x = 26
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = new Array(30001).fill(0);

// 다이나믹 프로그래밍 진행(보텀업)
for(let i = 2; i <= x; i++) {

  // 현재의 수에서 1을 뺀 경우
d[i] = d[i - 1] + 1;

  // 현재의 수가 2로 나누어 떨어지는 경우
  if(i / 2 == 0) d[i] = Math.min(d[i], d[parseInt(i / 2)] + 1)
  
  // 현재까지 구한 i를 1로 만들기위한 최적의 해와 i/2 나눈값을 1로 만들기위한 최적의 해와 1을 더한 값과 비교해서 더 작은 취하게함.
  
  
  // 현재의 수가 3으로 나누어 떨어지는 경우
  if(i / 3 == 0) d[i] = Math.min(d[i], d[parseInt(i /3)] + 1)
  
  // 현재의 수가 5로 나누어 떨어지는 경우 
  if(i / 5 == 0) d[i] = Math.min(d[i], d[parseInt(i /5)] + 1)
  
  
}

console.log(d[x])