[프로그래머스] 258705 : 산모양타일링 [JAVA] Lv.3

프로그래머스

문제 풀이 설명 (summary)

• 전체 모양을 2차 배열모양으로 변경
• 삼각형 모양이 있는 위치를 좌표로 변환
• 홀수, 짝수에 따라 나올 수 있는 경우의 수 구분
• (DP) 각 인덱스에 나올 수 있는 경우의 수를 누적 
• 마지막 인덱스를 출력 (모든 누적 결과 합)

 

문제 풀이 접근법

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

 

풀이 코드 (Code)

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;
    }
}

 

문제 링크(Link) 

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