로직

logic

• 가능한 연산 아래 3가지를 가장 적게 사용해서 ,연산 최소 횟수 구하기
• X%3==0 --> X/3 또는 X%2==0 --> X/2 또는 X-1
• greedy? dp!!
• 내가 생각한 처음 최적 방법이 끝까지 반례없이 적용가능?
• 그중에서 최소를 구해야함? => dp
• 단순히 10//2 -> 5-1 -> 4//2 -> 2//2 =1 (답 4)가 아니라
  -1해서 계산한 값이 더 큰지 바로 나눗셈으로 들어가는 값이 더 작은 지 체크를 해줘야함
• 역으로 배열 순회하면서 1씩 증가해주면서 현재값이 작은지 3이나 2로 나눈 몫+1이 더 작은지 비교하기!

풀이

const test1 = 10;
const test2 = 123114;
const test3 = 121;
const test4 = 5;
const convert_to_one = (n: number) => {
  const arr: Array<number> = new Array(n + 1);
  arr.fill(0);

  arr.map((item, idx) => {
    if (idx >= 2) {
      arr[idx] = arr[idx - 1] + 1;
      if (idx % 3 === 0) {
        arr[idx] = Math.min(arr[idx], arr[idx / 3] + 1);
      }
      if (idx % 2 === 0) {
        arr[idx] = Math.min(arr[idx], arr[idx / 2] + 1);
      }
    }
  });
  return arr[n];
};
console.log(convert_to_one(test1));
console.log(convert_to_one(test2));
console.log(convert_to_one(test3));
console.log(convert_to_one(test4));