재귀호출 :: 하나의 트리 구조로 호출하기 [2]

tony·2023년 5월 1일

코딩테스트-알고리즘

목록 보기

2/10

Promblem❗

📖 1이 되는 순간까지

정수 N이 주어집니다. N이 짝수이면 2로 나누고, 홀수이면 3으로 나눈 몫을 취하는 작업을 반복하다가 그 값이 1이 되면 그때까지 진행한 작업의 횟수를 구하는 프로그램을 재귀 함수를 이용하여 작성해보세요.

입력 형식

첫 번째 줄에 정수 N이 주어집니다.

1 ≤ N ≤ 1,000,000

출력 형식

첫 번째 줄에 나누는 작업의 횟수를 출력합니다.

입출력 예제

예제1

입력:

230

출력:

6

예제 설명

첫 번째 예제에서 입력으로 230이 주어집니다. 230에서 1이 될때까지 나누는 작업을 진행하면, 230 -> 115 -> 38 -> 19 -> 6 -> 3 -> 1 입니다. 총 6번 진행합니다.

제한

시간 제한: 1000ms 메모리 제한: 80MB

Solve 💡

내 답이 틀리지는 않았다. 효율적인 부분에서도 틀리지 않았다.

다만 재귀호출이 이진트리와 같이 호출부와 리턴부로 나눠진다는 것에 집중해보자.

리턴해야할 값 : 각 단계 별로 증가된 count값

호출부 : 초기 입력단계로부터 각 재귀호출 단계별로 연산된 값

내 풀이 :: 증가된 count 값을 호출부로 넘김
나는 호출부에 각 단계별 연산값 뿐만 아니라 증가된 count값을 넘겼다.

```java
package Codetree.ReturnRecursive;

import java.util.Scanner;

public class UntilOne {
    public static void main(String[] args) {
        /* input */
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        /* calc */
        int divideCount = getDivideCount(n, 0);
        /* result */
        System.out.println(divideCount);
    }

    private static int getDivideCount(int n, int count) {
        /* 종료조건 :: 몫이 1이 될 때까지 */
        if (n == 1)
            return count;
        /* 짝/홀에 따른 나눔 재귀호출 */
        // 짝수 :: func(n/2,count++)
        if (n % 2 == 0) {
            System.out.print("n/2 : " + (n / 2));
            System.out.println("count++ : " + (count + 1));
            return getDivideCount(n / 2, ++count);
        }
        // 홀수 :: func(n/3,count++)
        System.out.print("n/3 : " + (n / 3));
        System.out.println("count++ : " + (count + 1));
        return getDivideCount(n / 3, ++count);
    }
}
```

해설 풀이 :: 증가된 count값을 리턴부에 위임
해설에서는 증가된 count값은 리턴 시에 계산되게끔 리턴부에 위임하였다.

import java.util.Scanner;

public class Main {
    // n에서 시작하여 1이 되기 위해
    // 거쳐야하는 횟수를 반환하는 함수입니다.
    public static int getNum(int n) { 
        // 1이면 더 이상 진행할 작업이 없으므로 0회가 더 필요합니다.
        if(n == 1)
            return 0;

        // 짝수라면 2로 나눠 진행했을 때의 횟수 + 1번이 소요됩니다.
        if(n % 2 == 0)
            return getNum(n / 2) + 1;
        // 홀수라면 3으로 나누었을 때의 몫을 가지고 진행했을 때의 횟수 + 1번
        // 소요됩니다.
        else
            return getNum(n / 3) + 1;
    }

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

        // 변수 선언 및 입력:
        int n = sc.nextInt();

        System.out.println(getNum(n));
	}
}