코드업(codeup) 3733 : 우박수 길이 (3n+1) (large) C언어

▶문제 : 우박수 길이 (3n+1) (large) (codeup.kr)

우박수 길이 (3n+1) (large)

 

▶코드 작성

#include <stdio.h>

int memo[100000001];

int func(long long n) {
    if (n == 1) return 1;
    if (n > 100000000) {//1억을 초과하였을 때
        if (n % 2 == 0) return func(n / 2) + 1;//memo배열 없이 계산
        else return func(n * 3 + 1) + 1;
    }
    if (memo[n] != 0) return memo[n];//memo배열에 저장되어있다면 반환
    if (n % 2 == 0) return memo[n] = func(n / 2) + 1;//memo배열에 길이 저장
    else return memo[n] = func(n * 3 + 1) + 1;//memo배열에 길이 저장
}

int main() {
    int a, b, num = 0;
    scanf("%d %d", &a, &b);
    for (int i = a; i <= b; i++) {
        int n = func(i);
        if (n > memo[num]) num = i;//큰 값 찾기
    }
    printf("%d %d", num, memo[num]);
}

 

▶해석

재귀와 메모이제이션을 이용해 문제를 풀 수 있었다.

하지만 이 문제는 n이 홀수일 때 n*3+1해 주는 것에서 생각을 해야 한다.

n이 1억을 넘으면 memo배열을 이용할 수 없으므로 n값을 long long으로 선언하여 memo배열 없이 길이를 구하였다.