mo != 2가 문제가 아니라 min3 이 0일 경우 무시하는 코드가 없어서 0이 최소값이 되고 그 경우 10000 값으로 대체가 되는 것이 문제입니다.
(11,0)->(10,1)->(9,2)->(3,0)->(1,0) 해서 4가 답이 나와야 하는데,
(9,2) 에서 mo == 2 이니 min3 = 0 이 되고 39라인에서 min = 0, 42 라인에서 10000 이 됩니다.
따라서 (9,2)는 값이 너무 커져서 무시가 될꺼고
결국 (11,0)->(10,1)->(5,0)->(4,1)->(2,0)->(1,0) 으로 답이 5가 나오게 됩니다.
min 값을 좀더 이쁘게 구하는 방법 중의 하나는...
#include <iostream> using namespace std; int func(int a,int mo) { int min1, min2, min3, min; min1 = min2 = min3 = 1000005; if (a == 1) return 0; if (a == 2 || a == 3) return 1; if (a % 3 == 0) min1 = func(a / 3, 0)+1; if (a % 2 == 0) min2 = func(a / 2, 0)+1; if (mo != 2) // 이부분! { mo++; min3 = func(a - 1, mo)+1; } if (min1 < min2) min = min1; else min = min2; if (min3 < min) min = min3; return min; } int main() { int N,result; cin >> N; result = func(N, 0); cout << result; }
plan222 4년 전
중간에 if(mo !=3) 이부분을 원래 if(mo != 2)로 했었습니다.
1을 3번 연속 빼서 최소의 경우가 나올 수없다고 생각해서, 1을 빼는걸 2번 연속했으면 더이상 1을 빼지 말라는 의미로 썻습니다.
그러면 10을 입력하면 3은 잘 나오는데
11을 입력하면 5가 나오네요.
왜그런지 한참봐도 모르겠어서 그냥 저걸 3으로 바꿔보니 4가 나와요... 풀었는데 이유를 모르겠어요...
func(10,0) = 3 인데
func(10,1) =4 다??
func(10,1)은 func(9,2)를 부를 수 있고 이거는 2가 나올텐데 왜그럴까요?
+그리고 3개의 값에서 0이 아닌 값중에서 최솟값을 찾는 쉬운 코드도 알 수 있을까요?
밑에 비교하는 식이 매우 더러워서 부끄럽네요