문제

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
2. Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’. Leetcode

코드

int result = INT_MAX;

void get_steps(int cur, int pasted, int step, int n) {
  if (cur == n) {
    result = min(result, step);
    return;
  } else if (cur > n) return;

  // paste
  get_steps(cur + pasted, pasted, step + 1, n);
  // copy
  if (cur != pasted) get_steps(cur, cur, step + 1, n);
}

int minSteps(int n) {
  if (n == 1) return 0;
  
  get_steps(1, 1, 1, n);
  return result;
}

풀이

2가지 동작 중 선택해서 step을 늘려가면 된다. cur을 현재 개수, pasted를 복사된 개수라고 했을 때, Paste의 경우 cur = cur + pasted가 되며 Copy All의 경우 pasted = copy가 된다.

규칙을 찾아서 해결하는 풀이도 보인다.

int res = 0;
for (int i = 2; i <= n; i++){
  while (n % i == 0) {
    res += i;
    n /= i;
  }
}
return res;

81 -> 81 / 3 = 27 -> 27 / 3 = 9 -> 9 / 3 = 3 -> 3 이런 방식인 것 같다. solution