[Baekjoon] 5393. 콜라츠

mori·2024년 8월 29일

Problem 💻

문제

상근이는 3n+1으로 유명한 문제인 콜라츠 추측을 풀기 위해 나무판와 밧줄을 구매했다. 나무판의 길이는 무한히 크고, 왼쪽에서 오른쪽으로 1m 간격으로 구멍이 뚤려져 있다. i번째 구멍은 자연수 i를 의미한다. 모든 짝수번째 구멍 m에는 m번째와 m/2번째 구멍을 연결하는 밧줄이 연결되어 있다. 또, 모든 홀수번째 구멍 n에는 n번째와 3n+1번째 구멍을 연결하는 밧줄이 연결되어 있다.

상근이는 자신의 작품을 들고 신입생 환영회에 가서 홍보를 하려고 한다. 하지만, 나무판의 길이가 무한대이기 때문에, 들고갈 방법이 도저히 생각나지 않았다. 따라서, 상근이는 밧줄을 적절히 잘라서 처음 N개 구멍만 들고가려고 한다. 이때, 밧줄을 최소 몇 개만 자르면 처음 N개 구멍만 있는 나무판을 들고 갈 수 있을까?

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 문제에서 설명한 N이 포함된 한 줄로 이루어져 있다. (0 ≤ N ≤ 109)

출력

각 테스트 케이스에 대해서, 밧줄을 최소 몇 개 자르면 되는지 출력한다.

출력 예시

예제 입력

예제 출력

10
200
3000

Approach

알고리즘

입력 → 기본적 연결 + 추가적 연결 계산 = 최소 밧줄 개수 → 출력

의문점

문제 이해하기
- 주어진 구멍의 개수 N에 대해 밧줄을 최소 몇 개 자르면 처음 N개 구멍만 남길 수 있는지 구하는 문제
- 결론 : 입력값을 받아 밧줄을 잘라야 하는 최소 개수를 구해라! / N번째까지의 구멍만 남기고 나머지 구멍으로 연결된 모든 밧줄을 자른다. 밧줄을 최소한 몇 개 자를 것인지 계산
- 예시 설명
  - 예시 입력
```
3       <- 테스트 케이스의 개수
12      <- 첫 번째 테스트 케이스의 N 값
240     <- 두 번째 테스트 케이스의 N 값
3600    <- 세 번째 테스트 케이스의 N 값
```
  - 예시 출력
```
10      <- 첫 번째 테스트 케이스의 결과
200     <- 두 번째 테스트 케이스의 결과
3000    <- 세 번째 테스트 케이스의 결과
```
  - 첫 번째 테스트 케이스 N값 예시 설명
    
    예시 1: N = 12
    - 1번 구멍은 4번 구멍과 연결됩니다. (홀수이므로 3*1 + 1 = 4)
    - 2번 구멍은 1번 구멍과 연결됩니다. (짝수이므로 2/2 = 1)
    - 3번 구멍은 10번 구멍과 연결됩니다. (홀수이므로 3*3 + 1 = 10)
    - 4번 구멍은 2번 구멍과 연결됩니다. (짝수이므로 4/2 = 2)
    - 5번 구멍은 16번 구멍과 연결됩니다. (홀수이므로 3*5 + 1 = 16)
    - 6번 구멍은 3번 구멍과 연결됩니다. (짝수이므로 6/2 = 3)
    - 7번 구멍은 22번 구멍과 연결됩니다. (홀수이므로 3*7 + 1 = 22)
    - 8번 구멍은 4번 구멍과 연결됩니다. (짝수이므로 8/2 = 4)
    - 9번 구멍은 28번 구멍과 연결됩니다. (홀수이므로 3*9 + 1 = 28)
    - 10번 구멍은 5번 구멍과 연결됩니다. (짝수이므로 10/2 = 5)
    - 11번 구멍은 34번 구멍과 연결됩니다. (홀수이므로 3*11 + 1 = 34)
    - 12번 구멍은 6번 구멍과 연결됩니다. (짝수이므로 12/2 = 6)
      
      여기서 12번째 구멍까지 연결된 구멍들 중에서 12번 이후의 구멍들(예: 16, 22, 28, 34)로 연결된 밧줄을 끊어야만 1번부터 12번 구멍만 남길 수 있다.
    12번 이후의 구멍과 연결된 밧줄을 끊어야 하는 구멍들
    - 5번 구멍 → 16번 구멍 (N = 12 초과, 잘라야 함)
    - 7번 구멍 → 22번 구멍 (N = 12 초과, 잘라야 함)
    - 9번 구멍 → 28번 구멍 (N = 12 초과, 잘라야 함)
    - 11번 구멍 → 34번 구멍 (N = 12 초과, 잘라야 함)
      
      이렇게 4개의 밧줄은 확실히 잘라야 한다.
    추가적으로 잘라야 할 밧줄들
    
    콜라츠 추측에 따라, 특정 구멍들이 계속해서 큰 번호의 구멍으로 연결되는 방식이 반복되기 때문에, 추가적인 자르기가 필요합니다. 즉, 12번째 구멍까지 모든 가능한 연결을 추적하여 더 많은 연결이 발생할 수 있는 경우를 모두 고려해야 한다.
    
    N = 12 범위 내에서 연결 관계:
    1. 10번 구멍 → 5번 구멍
      - 10번 구멍은 5번 구멍으로 연결된다. 그러나, 5번 구멍은 이미 16번 구멍으로 연결되어 있기 때문에 16번 구멍으로의 연결을 잘라야 한다. 10번 구멍의 연결을 유지하기 위해 추가적인 밧줄 자르기가 필요하다.
    2. 3번 구멍 → 10번 구멍
      - 3번 구멍은 10번 구멍으로 연결된다. 10번 구멍은 다시 5번 구멍으로 연결되므로, 이 연결을 유지하려면 5번 구멍의 연결을 잘라야 한다.
    3. 1번 구멍 → 4번 구멍
      - 1번 구멍은 4번 구멍으로 연결되며, 이 연결도 추가적인 밧줄 자르기를 필요로 할 수 있다.
    4. 7번 구멍 → 22번 구멍
      - 7번 구멍은 22번 구멍으로 연결되며, 이미 잘라야 할 밧줄에 포함된다.
    5. 8번 구멍 → 4번 구멍
      - 8번 구멍이 4번 구멍으로 연결되며, 이 연결 역시 N 이내에서 밧줄 자르기를 요구할 수 있다.
    6. 6번 구멍 → 3번 구멍
      - 6번 구멍이 3번 구멍으로 연결된다. 이 연결을 고려하면 전체 밧줄을 잘라야 하는 상황이 발생한다.
    결론
    
    요약하면, 구멍 12번까지만 고려했을 때, 다음의 10개의 밧줄을 잘라야 한다 :
    1. 5번 구멍 → 16번 구멍
    2. 7번 구멍 → 22번 구멍
    3. 9번 구멍 → 28번 구멍
    4. 11번 구멍 → 34번 구멍
    5. 10번 구멍 → 5번 구멍
    6. 3번 구멍 → 10번 구멍
    7. 1번 구멍 → 4번 구멍
    8. 8번 구멍 → 4번 구멍
    9. 6번 구멍 → 3번 구멍
    10. 10번 구멍 → 5번 구멍 (추가적인 고려)
    이렇게 총 10개의 밧줄을 잘라야 1번부터 12번까지의 구멍만 남길 수 있다.
관건은 ‘N보다 작은 수에서 얼만큼의 연결고리가 생겨나는 지’이다.
주의 : n이 홀수일 때 3n+1은 무조건 짝수임으로 N보다 작은 범위에서ㅁ는 짝수 연결고리를 구한 상황이 발생해 중복이 발생한다.
- 홀수 구멍 n에서 3n + 1을 계산하면 결과가 항상 짝수이다. 따라서, 3n + 1에서 발생하는 짝수 연결고리는 이미 처리된 짝수 구멍과 중복될 수 있다.
- 예를 들어, 구멍이 5인 경우 : 3*5+1 =16 / 16은 짝수니까 16과 8을 연결하는 밧줄이 필요 → 하지만 8은 이미 4와 연결된다.
중복을 피하기 위해 특별 처리가 필요하다! ⇒ (x % 6 === 0 || x % 6 === 4)
- 위 예시처럼 중복 연결이 발생하는데 이를 방지하기 위해 필요하다!

요약

콜라츠 추측
- 1부터 시작하는 수열이 해당 규칙을 반복적으로 적용되며 어떤 수든지 결국 1로 수렴한다.
- 규칙 : n이 짝수라면 2로 나누고, n이 홀수라면 3을 곱하고 1을 더한다. 이 과정을 반복해서 n이 1이 되는지를 확인한다.
해당 문제는 콜라츠 추측을 직접적으로 계산하거나 검증하는 것이 아닌, 주어진 문제의 요구사항을 해결하기 위한 알고리즘으로 작성되었다. 콜라츠 추측의 규칙에 따라 구멍들이 연결되어 있다는 점에서 간접적으로 관련이 있는 문제이다.
콜라츠가 어려운거야 문제가 어려운거야…🥲

Solution 💡

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 첫 번째 줄 테스트 케이스 개수
const T = parseInt(input[0]);

for (let i = 1; i <= T; i++) {
    // 각 테스트 케이스의 수 => 테스트 케이스 개수 제외한 각 N값만 for문 적용
    const x = parseInt(input[i]);
    let ans = 0; // 자를 밧줄 개수 저장할 변수

		//[짝,홀수 구분 : 기본적인 밧줄 개수 계산]
    if (x % 2 === 0) {
        ans += x / 2;
    } else {
        ans += Math.floor(x / 2) + 1;
    }

		//[불필요한 반복 줄이기 / 추가적인 밧줄 개수 계산]
    // x가 6의 배수이거나, 6으로 나눈 나머지가 4인 경우, **3의 배수와 관련된 밧줄의 개수를 계산**
    if (x % 6 === 0 || x % 6 === 4) {
        ans += Math.floor(x / 3);
    } else {
        // 나머지가 0이 아니고 4도 아닌 경우, 올림을 적용하여 밧줄의 개수를 계산
        //x가 3의 배수가 아니거나 6의 배수가 아닐 때 더많은 연결이 발생하기 때문에 더 많은 밧줄을 잘라야 함!
        ans += Math.floor(x / 3) + 1;
    }

    // 계산된 밧줄의 개수를 출력합니다
    console.log(ans);
}