[코틀린, 자바] 백준 14651 - 걷다보니 신천역 삼 (Large) (boj kotlin java)

문제 : boj14651

 

  우선 3의 배수를 판정하는 방법부터 알아보자. 이 경우 수 A의 모든 자리의 숫자의 합이 3의 배수라면 A도 3의배수이다(정수론). 그럼 이 문제는 N자리 숫자에 대해, N번의 선택을 거친 결과 모든 자리 수의 합이 3의 배수인 경우의 수를 찾는 문제인 셈이다. 물론 단순하게 brute force로 찾아보려 한다면 O(3^33333)이 필요하므로 불가능하다.

 

  DP로 생각해보자. dp[a][b]를 a번째 자리수까지 더했을 때의 합을 3으로 나눈 나머지가 b인 경우의 수로 정해보자. 그럼 a가 5일때까지만 살펴보자. (N=5)

 

1. 우선 a=1 일 경우 다음과 같이 될 것이다.

  또 이렇게 두면 '0으로 시작하는 수는 만들 수 없는 수 이삼' 부분을 별도로 처리하지 않아도 되기 때문에 dp의 초기값이기도 하다.

 

2. a=2일 때를 보자. 이 경우 3개로 나누어서 생각해야 한다.

2.1 a=1일 때의 결과에서 0을 더해주는 경우 따로 b값이 변경되지 않으므로 그대로 내려오면 된다.

2.2 a=1인 결과에서 1을 덧붙여주는 경우, 합계가 변경이 되므로 a=1인 결과에서 3으로 나눈 나머지가 0인 경우에 '1'을 붙여주면 3으로 나눈 나머지는 1이 될 것이다. 따라서 dp[2][1] += dp[1][0] 가 된다. 다만 이때 dp[1][2]인 결과는 1을 더해주면 dp[2][0]에 포함이 되어줘야 한다. 이걸 편하게 처리하기 위한 부분이 'idx=(i+j)%3' 부분이다.

 

2.3 이번엔 2를 덧붙여주는 경우이다. 마찬가지로 진행하면 된다.

 

3. 이제 a=5 까지 마찬가지 방식으로 진행하면 되며 결과는 다음과 같다. 최종적으로 dp[5][0]이 답이 된다.

------------

 

인줄 알았는데!

 

근데 저도 글 쓰면서 표 만들다보니 이상해서 알았는게 결국 a=2부터는 b가 몇이든 모든 수가 동일한걸 볼 수 있다. 결국 어차피 이전의 3군데에서 동일하게 내려오다보니 이렇게 된다(어차피 0,1,2 세개의 수만 사용하므로). 따라서 그냥 dp[a]만 가지고, dp[2]=2 부터 dp[3]=dp[2]*3%MOD 이런식으로 진행해도 문제가 없다. 물론 위에서 말한대로 해도 정해이긴하다.

 

추가로 어차피 바로 직전의 데이터만 있으면 되므로 사실 dp[a]도 필요없다. 그냥 변수 하나면 된다.

 

-------

 

이하 코드에서 kotlin은 dp로 푼 코드이고, java코드는 글 작성하다가 생각난 더 효율적인 방법으로 짠 코드이다.

 

 

 

코드(kotlin) : github

import java.io.BufferedReader
import java.io.InputStreamReader

const val MOD = 1_000_000_009
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    var dp = arrayOf(0, 1, 1)
    repeat(n-1) {
        var tmp = Array(3) {0}
        for (i in 0..2) {
            for (j in 0 .. 2) {
                val idx = (i+j)%3
                tmp[idx]+=dp[j]
                tmp[idx]%=MOD
            }
        }
        dp = tmp
    }
    println(dp[0])
}

 

 

코드(java) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static final int MOD = 1_000_000_009;
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if (n==1) {
            System.out.println(0);
            return;
        }
        int answer = 2;
        for (int i = 2; i < n; i++) {
            answer = (int) (1l*answer*3%MOD);
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}