웹찢남

10의 경우 나누기 2를 먼저하면 안되고 -1을 하고 나누기 9를 하는게 가장 빠르다. 그냥 WHILE문으로 조건을 따져 구해볼까 했으나 조건을 찾는게 어려울 것 같아 DP로 풀었다. A=int(input()) dp=[0]*(A+1) dp[1]=0 for i in range(2,A+1): dp[i]=dp[i-1]+1 if(i%2==0 and dp[i]>dp[i//2]+1): dp[i]=dp[i//2]+1 if(i%3==0 and dp[i]>dp[i//3]+1): dp[i]=dp[i//3]+1 print(dp[A]) 위처럼 풀면 간단하게 정답을 구할 수 있다. 낮은 배열부터 최소의 경우를 따져 배열에 집어넣고 그러다 보면 결국 마지막 값까지 이를 사용해 구할 수 있다.