[백준] Ezreal 여눈부터 가네 ㅈㅈ (20500) Java

문제 링크

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

20500번: Ezreal 여눈부터 가네 ㅈㅈ

 

문제 요약

0으로 시작하지 않고 1과 5로만 구성된 N자리 양의 정수 중에서, 15의 배수가 몇 개인지 구하시오.

 

입력

자리수 N이 주어진다.

 

출력

문제의 답을 1,000,000,007로 나눈 나머지를 출력한다

 

접근법

15의 배수 판별법과 DP를 적용해서 풀 수 있었다.

 

일단 단순하게 완전 탐색으로 풀 수 없는 이유는,

1과 5로만 구성된 N자리의 수를 만들 수 있는 경우의 수는 2^N (N자리 숫자의 각 자리수가 1 또는 5인 모든 경우의 수)

이때 N이 최대 1515이므로 2^1515개의 숫자를 전부 탐색하는 것은 불가능하다.

 

뭐 가능하다고 해도, 1515자리 수를 만들어서 저장한다음 그걸 15로 나눠 보는 것 자체가 힘들 것이다. BigInt같은 클래스를 따로 구현해야만 가능하니까 말이다.

 

그래서 어떻게 풀까 삽질을 좀 하다가, 구글링을 해서 DP로 풀 수 있다는 사실을 알아내서 그렇게 풀어봤다.

 

먼저 15의 배수 판별법은 다음과 같다.

1. 일의 자리가 0 또는 5이고,
2. 모든 자리수의 합이 (일의 자리 포함) 3의 배수인 숫자는 15의 배수이다.

그런데 문제의 조건에서 1과 5로만 구성된 숫자라고 했으므로 일의 자리는 5로 고정되어야 함을 알 수 있다.

 

그리고 2번째 조건에 의해 1515자리의 숫자를 15로 나눠서 나머지가 0인 걸 알아볼 필요가 없고, 그냥 각 자리수의 합이 3의 배수인 것만 확인해보면 된다는 것을 알 수 있다. 모든 자리수가 전부 5인 1515자리의 숫자라도, 자리수의 합이 해봤자 5 * 1515 = 7575 이므로 충분히 연산과 저장이 가능한 범위의 숫자임을 알 수 있다.

 

그럼 이 사실을 가지고 DP를 적용해보자.

DP는 일종의 점화식 같은 개념으로, 이전에 기록해둔 (optimal한) 값을 이용해서 현재의 답을 찾는 것이라고 볼 수 있다.

 

이 문제에서는 1과 5 이 두가지의 숫자만 사용할 수 있으므로,

자리수가 하나 늘어날 때

1. 맨 앞자리에 숫자 1이 추가되는 경우
2. 맨 앞자리에 슷자 5가 추가되는 경우

이렇게 두 가지의 경우만이 존재하는 것을 알 수 있다.

 

이렇게 만들어진 숫자가 15 배수 판별법에 의해 각 자리수의 합이 3의 배수인지만 확인하면 되는데 (일의 자리는 5로 고정해 놨다고 가정했으므로 패스) 이 부분에서 DP를 이용해서 아주 간단하게 문제를 풀 수 있다.

 

1과 5로만 이루어진 자리수가 K인 숫자가 있을 때, 모든 자리수의 합에 3으로 나머지 연산을 하면 다음과 같은 3가지 경우가 존재한다.

1. 모든 자리수의 합을 3으로 나눴을 때 나머지가 0인 경우
   • 맨 앞에 1을 추가해서 K + 1자리 숫자를 만드는 경우, 모든 자리수의 합을 3으로 나눴을 때 나머지가 1이 된다
   • 맨 앞에 5를 추가해서 K + 1자리 숫자를 만드는 경우, 모든 자리수의 합을 3으로 나눴을 때 나머지가 2가 된다
2. 모든 자리수의 합을 3으로 나눴을 때 나머지가 1인 경우
   • 맨 앞에 1을 추가해서 K + 1자리 숫자를 만드는 경우, 모든 자리수의 합을 3으로 나눴을 때 나머지가 2가 된다
   • 맨 앞에 5를 추가해서 K + 1자리 숫자를 만드는 경우, 모든 자리수의 합을 3으로 나눴을 때 나머지가 0이 된다
3. 모든 자리수의 합을 3으로 나눴을 때 나머지가 2인 경우
   • 맨 앞에 1을 추가해서 K + 1자리 숫자를 만드는 경우, 모든 자리수의 합을 3으로 나눴을 때 나머지가 0이 된다
   • 맨 앞에 5를 추가해서 K + 1자리 숫자를 만드는 경우, 모든 자리수의 합을 3으로 나눴을 때 나머지가 1이 된다

 

이 사실을 이용해서 자리수 K에서 모든 자리수의 합을 3으로 나눴을 때 나머지가 0, 1, 2인 숫자의 개수를 배열로 기록하면서 입력받은 N까지 반복을 하면 문제를 풀 수 있다.

int[][] dp = new int[N + 1][3];

dp[K][0, 1, 2] = 자리수 K에서 모든 자리수의 합을 3으로 나눴을 때 나머지가 0, 1, 2인 숫자의 개수.

 

dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % 1_000_000_007;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 1_000_000_007;
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 1_000_000_007;

위에서 언급한 내용을 코드로 표현했다. 이 코드를 입력받은 N 값만큼 수행하면 된다.

 

정답은 N자리 수에서 3으로 나눈 나머지가 0인 경우이므로 dp[N][0]이 된다.

 

일의 자리를 5로 고정해 놓는다는 가정 때문에 dp 배열을 초기화 할 때 예외가 생기는데, 그 부분은 코드에 주석으로 설명해 놨으니 코드를 참고하기 바란다.

 

 

시간 복잡도

O(N)

 

 

공간 복잡도

N * 3 * sizeof(int) bytes

 

 

풀면서 놓쳤던 점

처음에는  15의 배수 판별법을 이용해서 K 자리수에서 1과 5의 개수의 합이 K - 1이 되는 모든 경우를 (일의 자리는 5로 고정)를 탐색하면서, 모든 자리수의 합이 3의 배수일 때를 확인했다.

만약 3의 배수이면, (K - 1) 자리에서 5가 x개 존재할 때 (K - 1)Cx를 구해가며 그 값을 누적하는 식으로 풀었다.

 

이론상으론 가능하고, 시간 초과도 나지 않지만 N의 최댓값이 1515로 너무 크다는 것이 문제였다.

예를 들어 1515C1000 하면 엄청나게 큰 값이 나와서 해당 값을 배열에 저장할 수 없었다.

 

그래서 이 값들도 미리 1,000,000,007로 나머지 연산을 해서 저장하면 풀 수 있지 않을까 싶었는데,

조합을 구할 때 정수로 나누는 연산이 존재해서 나머지 연산을 하는 순간 나누어 떨어지지 않고 날아가는 값이 생겨버리기 때문에 문제가 생겨서 오답이 나왔다.

 

뭐 BigInt같은 방식의 클래스를 내가 구현한다면 문제를 풀 수야 있었겠지만 그야말로 배보다 배꼽이 큰 경우이고, 시간초과가 날 것 같기도 하다.

 

그래도 내가 열심히 짠 코드가 아까워서 여기다 남겨는 둔다.

import java.util.Arrays;
import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        int digits = sc.nextInt();

        if (digits == 1)
        {
            System.out.println(0);
            return;
        }

        if (digits == 2)
        {
            System.out.println(1);
            return;
        }

        long[] combArr = fillCombinationArr(digits);

        System.out.println(countMultiplesOf15(digits, combArr));
    }

    static long[] fillCombinationArr(int digits)
    {
        digits--;

        long[] combArr = new long[digits + 1];

        combArr[0] = 1;
        combArr[1] = digits;

        int maxIdx = digits / 2;
        for (int i = 2; i <= maxIdx; i++)
            combArr[i] = (combArr[i - 1] * (digits - i + 1) / i) % 10_000_000_000L;

        for (int i = maxIdx + 1; i < combArr.length; i++)
            combArr[i] = combArr[digits - i];

        return combArr;
    }

    static long countMultiplesOf15(int digits, long[] combArr)
    {
        long cnt = 0;

        digits--;

        for (int numOf5 = 0; numOf5 <= digits; numOf5++)
        {
            int sumOfDigits = (numOf5 + 1) * 5 + (digits - numOf5);

            if (sumOfDigits % 3 == 0)
                cnt = (cnt + combArr[numOf5]) % 1_000_000_007;
        }

        return cnt;
    }
}

 

 

이 문제에서 얻어갈 점

다이나믹 프로그래밍.

 

 

코드

import java.util.Scanner;

/* https://kloong.tistory.com/entry/Ezreal-여눈부터-가네-ㅈㅈ-20500-Java */

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int digits = sc.nextInt();

        //자리수 1부터 자리수 digits 까지의 값을 기록할 dp 배열
        //dp[K][0] -> 자리수 K인 1과 5로 이루어진 숫자 중
        //일의 자리가 5이고 모든 자리수의 합을 3으로 나눈 나머지가 0인 수의 개수
        int[][] dp = new int[digits + 1][3];

        /* 한 자리 숫자에는 15의 배수가 존재하지 않음.
         * 그리고 어차피 dp의 초기값이라 배열을 직접 초기화 해줘야 하는데 그냥 답 출력하는게 빠름.
         * 그래서 두 자리 숫자까지는 그냥 답 출력해버리고, 그 이후부터만 dp로 답 구해서 출력함*/
        if (digits == 1) {
            System.out.println(0);
            return;
        }

        if (digits == 2) {
            System.out.println(1);
            return;
        }

        /* 1과 5로 이루어진 두자리수 숫자는 원래 15, 51, 55가 있지만
         * 15의 배수는 일의 자리가 5여야 하므로 51의 경우를 반드시 제외해 줘야 한다!
         * 따라서 두자리수에 대한 dp 배열을 아래와 같이 초기화 해 줘야 함
         * 한자리수에 대한 dp 배열부터 초기화하지 않는 이유는 한자리수 dp 배열을 초기화 한다 치면
         * dp 배열의 의미에 따라 dp[1][0] = dp[1][1] = dp[1][2] = 0 이어야 하는데 그러면
         * dp[2][0 ~ 2]가 점화식에 의해 제대로 초기화 될 수가 없기 때문! */
        dp[2][0] = 1;
        dp[2][1] = 1;
        dp[2][2] = 0;

        //점화식을 통한 dp 초기화
        for (int i = 3; i <= digits; i++) {
            dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % 1_000_000_007;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 1_000_000_007;
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 1_000_000_007;
        }

        //문제에서 요구하는 정답은 N 자리수 숫자에서 15의 배수이므로
        //3으로 나눴을 때 나머지가 0인 숫자의 개수를 출력해야 한다
        System.out.println(dp[digits][0]);
    }
}