[BaekJoon] 28123번 - 삶, 우주, 그리고 모든 것에 관한 궁극적인 질문의 해답 [Java][C++]

문제 링크

---

1. 문제 풀이

$2^n$ 을 십진법으로 표기했을 때 자릿수 $k$ 와, 가장 높은 자리의 숫자 $x$ 가 주어졌을 때, $1$ 부터 $2^n$ 까지의 숫자 중 $4$ 로 시작하는 2의 거듭제곱의 수를 구해야하는 문제다. 2의 거듭제곱의 가장 높은 자리의 숫자를 추적하다보면 규칙을 발견할 수 있는데 아래 5가지 패턴의 조합으로 이루어진다는 것을 알 수 있다.

• 1 2 4 8
• 1 2 4 9
• 1 2 5
• 1 3 6
• 1 3 7

1 부터 쭉 나열하면 (1, 2, 4, 8), (1, 3, 6), (1, 2, 5), (1, 2, 4, 8), 1, … 이렇게 나아가는 걸 볼 수 있다.

가장 높은 자리의 수가 5 이상이면 다음 거듭제곱에서 다시 1이 되며 거듭제곱을 통해 자릿수가 올림되는 경우와 올림되지 않는 경우를 분류하면 해당 경우들만 존재한다. 특정 패턴이 끝나고 다음 패턴이 시작되면 자릿수가 하나 올라간 것도 알 수 있다. 따라서 $k$ 는 위 패턴이 등장한 횟수와 동일하다. 다만 가장 마지막 패턴은 완성되지 않아도 하나의 패턴으로 쳐진다.

위 패턴들을 보면 재밌는 사실을 알 수 있는데 4를 포함하는 패턴은 모두 길이가 4이고 4를 포함하지 않는 패턴은 길이가 모두 3이다. $k$ 가 모든 패턴의 개수이므로 전체 수열의 길이에서 $3 \times k$ 를 빼주면 4의 개수를 바로 구할 수 있다.

$n$ 이 패턴의 끝이면 위 방식으로 바로 구하면 되지만 패턴의 중간에서 끝나면 케이스를 나누어줘야 한다. 이를 위해 가장 최근에 끝난 패턴과 현재 진행되다만 패턴으로 나누어줬는데 위 5가지 패턴의 각 수에 대해 1은 하나 전, 2와 3은 두 개 전, 4부터 7은 세 개 전, 8과 9는 4개 전으로 이동하면 이전 패턴의 끝인걸 알 수 있다. 이러면 이전에 닫힌 패턴에서 $3 \times (k - 1)$ 을 빼주는 것으로 이전에 닫힌 패턴에 해당하는 수까지 등장한 4의 개수를 구할 수 있다. 4, 8, 9의 경우 현재 진행되다만 패턴에도 4가 포함되는데 이를 조건문으로 분기처리할 수도 있지만 그냥 해당 수들이면 한 칸 덜가서 +1 한 것과 동일한 결과가 나올 수 있게 해줬다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = {0, 1, 2, 2, 2, 3, 3, 3, 3, 3};

        long n = Long.parseLong(st.nextToken());
        long k = Long.parseLong(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        System.out.println(n - arr[x] - 3 * (k - 1) + 1);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int arr[10] = {0, 1, 2, 2, 2, 3, 3, 3, 3, 3};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    long long n, k, x;
    cin >> n >> k >> x;
    cout << n - arr[x] - 3 * (k - 1) + 1;
}

---