모든 3의 배수는 n/3이 두 번 걸리는 (n -1) / 2 보다 작아서 굳이 n-1과 비교를 하지 않는 것 아닐까요
반면에 40과 같은 2의 배수는 40 - 1 / 3으로 13에 도달하는 동안 2로 두 번 나누면 10에 도달할 수 있어서 (반면에 10이라면 10-1이 10/2보다 빠르죠) -1과 비교를 하는 것 같습니다
물론 숫자가 더 작다고 1로 만드는 데 비용이 더 작은 것은 아니지만 그 차이는 3 또는 2의 배수가 아닐 때 근처에 있는 2의 배수로 가는 횟수의 차이일 뿐 이라서, 일반적으로는 성립하는 것 같네요
물론 저는 나누기 3이 돼도 n-1과 비교를 했습니다..하하
insu_nym 8년 전
안녕하세여 저는 위 문제를 거의 brute force에 가까운... 방법으로 해결했는데요...
제가 본 다른 소스는
나누기 삼이 되면 -> return recurse(n/3) + 1
안되면 -> min(recurse(n-1)+1, recurse(n/2) + 1) 식으로 풀었던데 위와 같은 우선순위는 어떻게 정하는게 맞나요?
써놓고도 무식이 통통한데 수학적 사고가 딸려서 그러니 이해해주세요ㅜㅜ