[BOJ 5393 // C++] 콜라츠

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 5393번 문제인 콜라츠이다.
문제는 아래 링크를 확인하자.

 

아래는 제출한 소스코드이다.

www.acmicpc.net/problem/5393

5393번: 콜라츠

문제 자체는 Collatz's conjecture을 언급하긴 하지만, 이 문제의 풀이와는 관련이 없다.

글쓴이는 이 문제를 3n+1과 관련된 밧줄의 수와 2n과 관련된 밧줄의 수로 구분지어 해결했다.

 

특히, 3n+1과 관련된 밧줄의 수의 규칙을 찾을 때, 홀수(주기 2)의 개수를 세야 하므로 modulo 6으로 규칙을 찾아준다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    int n, x; // n은 테스트케이스 수, x는 각 테스트케이스
    cin >> n;
    for (int i = 0;i < n;i++) {
        int ans = 0;
        cin >> x;
        if (x % 2 == 0) ans += x / 2; //2n과 관련된 밧줄의 개수
        else ans += x / 2 + 1;
        if (x % 6 == 0 or x % 6 == 4) ans += x / 3; //3n과 관련된 밧줄의 개수
        else ans += x / 3 + 1;
        cout << ans << '\n';
    }
}