알고리즘 기법 [다이나믹프로그래밍DP] 산모양타일링

기법

DP를 활용한 문제 풀이

 

체감 난이도

골드 1

 

설명

삼각형 모양이 있는곳을 모두 좌표로 취급했다. 
그리고 홀수, 짝수에 따라 나올 수 있는 모양을 각각 나누었다.

그리고 각 경우의 수마다 특정 인덱스로 이동해서 누적합을 저장하고
최종 맨 마지막 인덱스값을 출력

 

장점

• 정형화된 그리드 경로 문제는 BFS보다 DP가 훨씬 효율적입니다.
• BFS는 주로 최단거리 혹은 가중치가 있는 경로 탐색에 적합합니다.
• 현재 문제에서는 단순 경로 수 계산 문제이기 때문에, DP 방식이 시간적으로 훨씬 효율적인 것입니다.

 

코드

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {

        int n = 4;
        int[] tops = new int[]{1,1,0,1};

//        int n = 2;
//        int[] tops = new int[]{0,1};

//        int n = 10;
//        int[] tops = new int[]{0,0,0,0,0,0,0,0,0,0};

        solution(n, tops);
    }

    private static void solution(int n, int[] tops) {

        int[][] maps = new int[2][(n+1) * 2];
        for (int i = 1; i < maps[0].length; i++) {
            maps[1][i] = 1;
        }

        for (int i = 1; i <= tops.length; i++) {
            if (tops[i-1] == 1) maps[0][i * 2] = 1;
        }

        System.out.println(dp(maps));
    }

    private static int dp(int[][] maps) {
        int size = maps[0].length;
        int[] dp = new int[size];
        dp[1] = 1;

        for (int nowIndex = 1; nowIndex < size; nowIndex++) {
            // 인덱스가 짝수
            if (nowIndex % 2 == 0) {

                // 다이아몬드
                if (maps[0][nowIndex] == 1 && nowIndex + 1 < size) {
                    dp[nowIndex + 1] += dp[nowIndex] % 10007;
                }

                // 그냥 삼각형
                if (nowIndex + 1 < size) dp[nowIndex + 1] += dp[nowIndex] % 10007;

                // 오른쪽아래 사다리꼴
                if (nowIndex + 2 < size) dp[nowIndex + 2] += dp[nowIndex] % 10007;

                // 오른쪽아래 사다리꼴
                if (nowIndex + 2 == size) dp[nowIndex + 1] += dp[nowIndex] % 10007;
            }

            // 인덱스가 홀수
            else {
                // 그냥 삼각형
                if (nowIndex + 1 < size) dp[nowIndex + 1] += dp[nowIndex] % 10007;

                // 오른쪽아래 사다리꼴
                if (nowIndex + 2 < size) dp[nowIndex + 2] += dp[nowIndex] % 10007;
            }
        }

        return dp[size - 1] % 10007;
    }
}

 

알고리즘 기법을 이용한 문제 풀이 

https://school.programmers.co.kr/learn/courses/30/lessons/258705