[Baekjoon] 5393 콜라츠

https://www.acmicpc.net/problem/5393

3n+1 문제의 응용버전... 으로 보이지만 크게 관련이 있는지는 잘 모르겠다.

관건은 N보다 작은 수에서 얼만큼의 연결고리가 생기냐는 것.

먼저 N보다 작은 짝수의 연결고리를 공식으로 쉽게 구할 수 있다. (N / 2 + N % 2)

그 다음 홀수의 연결고리를 구하는데,

주의해야 할 것은 n이 홀수일 때 3n+1은 무조건 짝수이다. N보다 작은 범위에서는 짝수의 연결고리를 구한 상황이므로 중복된다.

그러므로 3n+1이 N보다 큰 경우에만 수를 세주면 된다.

#include <stdio.h>
#include <stdlib.h>
 
int main() {
    int testCase;
    scanf("%d", &testCase);
    
    for (int i = 0; i < testCase; i++) {
        int N;
        scanf("%d", &N);
 
        int count = N / 2 + N % 2;
        int t = (N - 1) / 3;
        for (int j = 1; j <= N; j += 2) {
            if (j > t) count++;
        }
 
        printf("%d\n", count);
    }
 
    return 1;
}

...라고 짜보았지만 시간초과가 걸렸다.

아무래도 홀수쪽도 수식으로 바꾸어야 될 것 같은데 일단은 패스해야겠다 ㅠㅠ