[swea] 7393. 대규의 팬덤활동

문제설명

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWm8gU7KljcDFASj&categoryId=AWm8gU7KljcDFASj&categoryType=CODE&problemTitle=%EB%8C%80%EA%B7%9C&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

기본아이디어

일단 기본적인 아이디어는 삐긋수라는 조건에 따라 N개의 값을 고르면서 만들어진 숫자열이 0~9까지 모두 포함하고 있는지를 체크하는 것이다.

먼저 이런 방식으로 풀면 정답은 무조건 나오지만, N이 커질수록 연산이 기하 급수적으로 늘어난다. 하나의 숫자에서 2개씩으로 늘어나니깐 O(2^N) 의 시간복잡도를 가진다. 연산을 줄이기 위해 중복된 연산을 없애야 한다. 그래서 피보나치 수열에서 사용한 메모이제이션을 사용하려고 한다. 한번 연산된 값을 배열에 저장해서 중복된 연산이 나왔을 때 배열에 저장한 값을 사용하는 방식이다.

 

그러려면 두 연산이 중복된 연산인지 확인해야 한다. 두 연산이 같은 연산이라는 조건은 1. 길이가 같아야 한다 2. 지금 끝값이 동일해야한다 3. 지금까지 숫자열에 포함된 숫자의 종류가 동일해야 한다. 

 

예를들어) 1 2 3 2 3 4  와 1 2 3 4 3 4 라는 두 숫자열을 보자 지금까지 나온 숫자열의 종류가 1, 2, 3, 4로 같고 길이가 같으며 끝값이 동일하다. 이런 경우에는 그 뒤에 나오는 경우의 수가 정확히 일치하므로 길이가 N에 도달했을 때 만족하는 숫자열의 경우의 수도 완전히 동일할 것이다.

 

따라서 3차원 배열을 만들어서 메모이제이션을 해서 중복연산을 없애주면 결과가 나온다.

구현코드

static final long MOD = 1000000000;
    static long[][][] dp;
    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(input.readLine());
 
        for(int test_case = 1; test_case <= T; test_case++){
            N = Integer.parseInt(input.readLine());
            dp = new long[N][10][1<<11];
            for(int i = 0; i < N; i++){
                for(int j = 0; j < 10; j++)
                    Arrays.fill(dp[i][j], -1);
            }
 
            long r = 0;
            for(int idx = 1; idx < 10; idx++){
                r = (r + fan(idx, 0, 0)) % MOD;
            }
            output.append("#" + test_case +" " + r + '\n');
        }
        System.out.println(output);
    }
    static int N;
    // num : 현재 끝값, len : 길이, state : 포함된 숫자
    static long fan(int num, int len, int state){
        if(num < 0 || num > 9)
            return 0;
 
        // 마지막, N개가 골라짐
        if(len == N-1){
            if((state | (1<<num)) == (1<<10)-1){
                return 1;
            }
            return 0;
        }
 
        if(dp[len][num][state] != -1)
            return dp[len][num][state];
 
        state |= (1<<num);
        return  dp[len][num][state] = (fan(num-1, len+1, state|(1<<num))
                + fan(num+1, len+1, state|(1<<num))) % MOD;
    }
 

 

정리, 기억할 내용

1. 그림 그려보자.

2. 반복되는 패턴을 찾아내자.

3. 메모이제이션!!