99클럽 코테 스터디 22일차 TIL [DP]

 

- 오늘의 학습 키워드 : DP

[문제 이름 : 산 모양 타일링 (프로그래머스 카카오 겨울 인턴십, LV 3)]
문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/258705

내가 작성한 코드는 아래와 같다.

class Solution {
    public int solution(int n, int[] tops) {
        int mod = 10007;
        int[][] dp = new int[n][2];
        
        // 초기값 풀이 그림 참고
        dp[0][0] = tops[0] == 1 ? 3 : 2; 
        dp[0][1] = 1;
        
        for (int i = 1; i < n; i++) {
            int mul1 = tops[i] == 1 ? 3 : 2;
            int mul2 = tops[i] == 1 ? 2 : 1;
            
            dp[i][0] = (dp[i - 1][0] * mul1 + dp[i - 1][1] * mul2) % mod;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
        }
        
        return (dp[n - 1][0] + dp[n - 1][1]) % mod;
    }
}

풀이 과정(풀이 시간 : 1시간 30분)

문제의 DP 점화식을 계산해보려고 하다 보니, 시간이 너무 오래 걸렸다. 실제 문제에서는 접근조차 못할 것 같다 .. 
아래 그림을 참고하여 문제를 이해하면 쉽게 풀 수 있다. (대회에서 이를 그리며 DP를 구할 수 있을지는.. 모르겠다 ㅠ)

내일은 인턴 직무로 우리은행에 지원해볼 예정이다.

프로그래머스

 

99클럽, Til, 개발자취업, 오블완, 코딩테스트준비, 티스토리챌린지, 항해99