백준 14650번: 걷다보니 신천역 삼 (Small)

문제 설명

• 0,1,2만 사용해 만들 수 있는 N자리 숫자 중 3의 배수의 개수를 구하는 문제입니다.
  N자리 숫자는 0으로 시작할 수 없습니다.

접근법

• i자리 숫자는 i-1자리 숫자 뒤에 0 또는 1 또는 2가 추가된 모양입니다.
  즉, (0,1,2로 만들 수 있는 모든 i자리 숫자의 개수)는 (0,1,2로 만들 수 있는 모든 i자리 숫자의 개수) x 3 입니다.
• 하나씩 계산해보면 다음과 같은 규칙이 나옵니다.
  • N=1일때
    • 0은 자연수가 아니기때문에 불가능하고 1 또는 2가 가능합니다.
  • N=2일때
    • N=1일때의 숫자 뒤에 0 또는 1 또는 2가 붙습니다.
      • 10, 11, 12
      • 20, 21, 22
  • N=3일때
    • N=2일때의 숫자 뒤에 0 또는 1 또는 2가 붙습니다.
      • 100, 101, 102
      • 110, 111, 112
      • 120, 121, 122
      • 200, 201, 202
      • 210, 211, 212
      • 220, 221, 222
• 각 자릿수의 합이 3의 배수면 전체 수는 3의 배수입니다. 각 자릿수의 합을 3으로 나눈 나머지를 기준으로 숫자를 분류하면 편합니다.
  • N=2일때
    • 자릿수의 합을 3으로 나눈 나머지가 1: 10, 22
    • 자릿수의 합을 3으로 나눈 나머지가 2: 11, 20
    • 자릿수의 합을 3으로 나눈 나머지가 0: 12, 21
  • N=3일때
    • 자릿수의 합을 3으로 나눈 나머지가 1: 100, 112, 121, 202, 211, 220
    • 자릿수의 합을 3으로 나눈 나머지가 2: 101, 110, 122, 200, 212, 221
    • 자릿수의 합을 3으로 나눈 나머지가 0: 102, 111, 120, 201, 210, 222
  • 재밌는건 같은 N에서 자릿수의 합을 3으로 나눈 나머지가 0인 숫자들, 1인 숫자들, 2인 숫자들의 개수가 계속 동일하다는 점입니다. 그 이유는 이전 숫자에서 각각 하나씩 경우의수가 증가하기 때문입니다. (N=2일때 10인 숫자로 N=3일때는 3가지 숫자를 만들 수 있고 그 수는 각각 3으로 나눈 나머지가 1,2,0인 경우에 포함됩니다.)
    • 덕분에 원래 N=k일때 3으로 나눈 나머지가 0인 숫자는 N=k-1일때 3으로 나눈 나머지가 1인 숫자+맨 뒤에 2를 붙인 수, N=k-1일때 3으로 나눈 나머지가 2인 숫자+맨 뒤에 1을 붙인 수, N=k-1일때 3으로 나눈 나머지가 0인 숫자+맨 뒤에 0을 붙인 수가 되지만 이를 고려하지 않고 단순히 숫자의 증가만 계산해줘도 됩니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] dp = new int[10];
		dp[2] = 2;
		for (int i = 3; i < dp.length; i++) {
			dp[i] = dp[i-1]*3;
		}
		System.out.println(dp[N]);
		
	}
}