insu_nym   10달 전

안녕하세여 저는 위 문제를 거의 brute force에 가까운... 방법으로 해결했는데요...


제가 본 다른 소스는

나누기 삼이 되면 -> return recurse(n/3) + 1

안되면 -> min(recurse(n-1)+1, recurse(n/2) + 1) 식으로 풀었던데 위와 같은 우선순위는 어떻게 정하는게 맞나요?


써놓고도 무식이 통통한데 수학적 사고가 딸려서 그러니 이해해주세요ㅜㅜ

indioindio   10달 전

모든 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   10달 전

아 감사합니다! 수능을 기점으로 뇌에서 수학을 격리시켜서 고생이네요! ㅜㅜ

wow1514   10달 전

bfs로 풀어도 풀리네요.

댓글을 작성하려면 로그인해야 합니다.