jojls1004   8달 전

최소 연산 횟수를 검사하는 알고리즘의 대략적인 설명입니다.

검사 과정

"3의 배수인가?" ┬ YES 입력값을 3으로 나눈 값을 새로운 입력값으로 해서 다시 검사, 검사횟수 +1

                           ┴ NO "2의 배수인가?" ┬ YES "2의 거듭제곱인가?" ┬ YES 검사횟수 +(지수), 검사 종료

                                                                                                     ┴ NO "1을 뺐을 때 3의 배수인가?" ┬ YES 입력값에 1을 뺀 값을 새로운 입력값으로 해서 다시 검사, 검사횟수 +1

                                                                                                                                                           ┴ NO 입력값을 2로 나눈 값을 새로운 입력값으로 해서 다시 검사, 검사횟수 +1

                                                          ┴ NO "입력값이 1이 아닌가?" ┬ YES 입력값에 1을 뺀 값을 새로운 입력값으로 해서 다시 검사, 검사 횟수 +1

                                                                                                         ┴ NO 검사횟수 +0, 검사 종료(입력값에 변화를 주다가 결국 1이 됐을 때)

검사 종료 후 검사 횟수가 최소 연산 횟수이므로 검사 횟수 출력.

단, 위 검사 과정은 초기 입력값이 1이 아닐 때만 작동하고, 초기 입력값이 1인 경우 바로 1 출력.

예시

초기 입력값 10

10 -> 3의 배수 X -> 2의 배수 O -> 2의 거듭 제곱 X -> 1 뺐을 때 3의 배수 O -> 입력값 9(10-1)로 변경, 현재 검사횟수 1(0+1) -> 9 -> 3의 배수 O 

-> 입력값 3(9/3)으로 변경, 현재 검사횟수 2(1+1) -> 3 -> 3의 배수 -> 입력값 1(3/1)로 변경, 현재 검사횟수 3(2+1) -> 1 -> 3의 배수 X -> 2의 배수 X 

-> 입력값 1이 아님 X -> 현재 검사횟수 3(3+0), 검사 종료

검사 결과 3

toonraon   8달 전

반례입니다

jojls1004   8달 전

반례1) 아 1 입력하면 1이 아니라 0이 나오는 게 맞네요 착각해서 괜히 처음에 조건문을 넣었네요!

나머지 반례도 찾아주셔서 감사합니다!

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