[AtCoder - ABC116 B] Collatz Problem

난이도: 128 // -55

 

태그

• Arithmetic

 

풀이

1. 무엇을 하면 될까?

문제에서 나온 대로, 입력받은 수에서 출발해서 함수를 계속 씌우다가, 어느 순간 본 적 있는 수가 나오면 그 때의 인덱스를 출력하면 됩니다.

물론 길어질 때를 대비해서, chk[x] = x가 나온 적이 있는가? 를 사용하는 것이 좋겠죠.

 

여담으로, 범위 내에서는 항상 ?, 1, 4, 2, 1, ...으로 반복되고, 이게 첫 반복이기 때문에

1의 위치 + 3을 해도 정답이 됩니다.

 

2. 조금 더 깊은 생각

'근데 이거 너무 커지지 않을까?' 하는 걱정이 생길 수도 있습니다.

다행히도, 문제 조건에서 1000000을 넘지 않는다고 친절히 제한을 걸었기 때문에 걱정 없이 구현하면 됩니다.

 

3. 코드

bool chk[1000020];
 
void Main(){
    int x; cin >> x;
    for (int ans = 1; ; ans++){
        if (chk[x]){ cout << ans; return; }
        chk[x] = 1;
        x = (x%2==0 ? x/2 : 3*x+1);
    }
}