forybm   1년 전

어떤 예제를 대입해봐도 다 답이 나오는데 말이죠 ㅠㅠ

yukariko   1년 전

정말 다 해보셨나요??

10을 넣어보니 4가 나옵니다.

10 -> 9 -> 3 -> 1로 3이 나와야합니다.

forybm   1년 전

정말 죄송하네요 .. ㅠㅠ 감사합니다 노력할께요

forybm   1년 전

생각보다 무지복잡하네요 ㅋㅋ

yukariko   1년 전

이 문제는 완전탐색+가지치기나 DP가 필요합니다.

DP에 대한 설명은

https://www.acmicpc.net/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95_-_dynamic_programming

를 참고해보세요.


forybm   1년 전

정말감사합니다.. 공부하고 답을한번 찾아내보겠습니다. 정말감사해요 !!

forybm   1년 전

후.. dp의 개념에대해 많이 공부해봤는데요 ㅠㅠ 이 문제에서는

dp문제를 어떻게 정의를 해야될가요..

힌트좀 주시면 안될까요?

저는 dp[n][1] 전 수에서 1을뺀것

dp[n][2] 전 수에서 2로 나눈것

dp[n][3] 전 수에서 3으로 나눈것 이렇게 잡았는데

솔직히 맞는지도 모르겠고 감이 없네요 ㅠㅠ

yukariko   1년 전

dp[n] = n으로 1을 만드는 최소횟수로 생각하면 dp[n+1] 이 어떻게 정의될 지 알 수 있을겁니다.

hjk0553   1년 전

n이 3으로 나누어 떨어지면 dt[n]=min(solve(n-1),solve(n/3))+1

n이 2으로 나누어 떨어지면 dt[n]=min(solve(n-1),solve(n/2))+1

n이 2와 3으로도 안 나누어 떨어지면 dt[n]=solve(n-1)+1 으로 정의하실 수 있습니다.

여기서 탐색 함수 solve(n)이란 n을 1로 만들기 위한 최소 연산 횟수를 의미합니다. (dt[n]도 마찬가지입니다.)

dt를 이용해 메모이제이션까지 해주시면 해결하실 수 있으실 듯 합니다.

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