99클럽 코테 스터디 22일차 - 프로그래머스 , 산 모양 타일

문제 풀이 예상 시간보다 지나가면 다른 해석을 보고 있습니다. 

문제

 

풀이

문제 해석

1. 입력으로 주어지는 n 만큼의 길이가 1인 삼각형이 거꾸로 있고 그에 맞춰 사다리꼴이 되도록 하는 삼각형이 생긴다.

2. 즉 윗변의 길이는 n이고 밑 변의 길이는 n+1이다.

3. 또 다른 입력으로 윗변과 맞닿도록 생성되는 삼각형의 위치가 주어진다.

4. 예를 들어 n이 4이고 다른 입력이 [1,1,0,1] 이면 뒤집힌 삼각형 중 세 번째 삼각형만 제외하고 마름모가 완성된다.

5. 이렇게 만들어진 모양을 삼각형 또는 그 삼각형 두개를 이어 붙인 마름모를 사용해서 빈 곳 없이 채우려고 할 때 경우의 수를 10007로 나눈 나머지를 출력해라

문제 풀이

1. dp로 풀이하면 된다.

2. 두가지로 나누어서 생각하면 그나마 이해하기 수월하다.

3. 오른쪽 삼각형을 마름모로 먹으면서 끝나는 경우(i)와 그렇지 않은 경우(j)로 나누면 된다.

4. i의 경우 또다시 i 경우로 종료되는 경우는 단 하나

5. i의 경우에서 j의 경우로 종료되는 경우는 tops가 존재할 때는 2 아니면 1

6. j의 경우에서 i 경우로 종료되는 경우는 단 하나

7. j의 경우에서 j의 경우로 종료되는 경우는 top가 존재 할 때 3 아니면 2

8. 점화식으로 표현하면 코드와 같아진다.

소스코드

class Solution {
    public int solution(int n, int[] tops) {
        //침범하면서 끝나는 경우
        int[] dp1 = new int[n];
        //나머지 경우
        int[] dp2 = new int[n];
        
        //초기값 설정
        dp1[0] = 1;
        dp2[0] = 2 + tops[0];
        
        for(int i=1;i<n;i++){
            dp1[i] = (dp1[i-1] + dp2[i-1]) % 10007;
            dp2[i] = (dp1[i-1] * (1 + tops[i]) + dp2[i-1] * (2 + tops[i])) % 10007;
        }
        
        return (dp1[n-1] + dp2[n-1]) % 10007;
    }
}

 

TIL

• 설명을 들어도 이해가 힘들다 너무 dp는 진짜 너무 어렵다.
• 반복해서 보는 방법밖에는 모르겠다. 나아질거라는 느낌이 안 든다.
• 모듈러 연산을 계속해서 해줘도 되는 이유는 모듈러의 성질 덕이다.
  • 두 수를 더한 뒤 나머지를 구하는 것과 각각의 수에 대해 나머지를 구하고 그 수를 나머지를 구한 값과 같다. 
  • 두 수를 곱한 뒤 나머지를 구하는 것과 각각의 수에 대해 나머지를 구한 뒤 그 수를 나머지를 구한값과 같다.
  • 이를 통해 오버플로우를 방지할 수 있다.