사다리꼴의 윗변의 길이를 나타내는 정수 n과 사다리꼴 윗변에 붙인 정삼각형을 나타내는 1차원 정수 배열 tops가 매개변수로 주어집니다. 이때 문제 설명에 따라 만든 모양을 정삼각형 또는 마름모 타일로 빈 곳이 없도록 채우는 경우의 수를 10007로 나눈 나머지를 return 하도록 solution 함수를 완성해 주세요.
제한사항
1 ≤ n ≤ 100,000
tops의 길이 = n
tops[i]는 사다리꼴의 윗변과 변을 공유하는 i+1번째 정삼각형의 위쪽에 정삼각형을 붙이는 경우 1, 붙이지 않는 경우 0입니다.
문제 해석
DP 문제인데 케이스 분해가 쉽지않은 문제.
일단 무엇을 DP로 해야하는가? 정삼각형이 위쪽이 있을경우 4개 없을경우 3개의 모습이 나타나난다는것은 알았다.
사다리꼴이 겹치는 부분이 있기때문에 그 부분을 기반으로 겹쳤을때 + 겹치지않았을때를 더하면 현재 내가 원하는 top[i]의 값이 나온다.
삼각형이 겹쳤을때는 다음에 나올수 있는 경우의 수는 (사라리꼴,삼각형) (삼각형,사다리꼴),(삼각형3) 이기에 3이고 아닌경우는 (사라리꼴,삼각형) (삼각형,사다리꼴)이다.
그렇다면 DP[n] = 3 adp[n-1] + 2 * dp[n-1]이라는건데 여기서 이전에 나올수있는 값을 생각해보면 위쪽 삼각형이 없는경우도 구해야한다.
따라서 다음과 같은 공식이 성립된다.
// 붙는 숫자는 adp[n-1],dp[n-1] 형태를 취했을때 가능한 다음횟수이다.
DP[n] = top[n]==1?3*adp[n-1] + 2*dp[n-1]:2*adp[n-1] + dp[n-1];이를 통하여 답을 구할수 있다.
코드
class Solution {
public int solution(int n, int[] tops) {
int oldtop = tops[0]==1?3:2;
int oldtopcut = 1;
int newtopcut =0;
int newtop = 0;
if(n==1) return oldtop+1;
for(int i=1;i<tops.length;i++){
newtopcut= oldtop+oldtopcut;
if(tops[i]==1){
newtop = oldtop *3 + oldtopcut*2;
}else{
newtop = oldtop *2 + oldtopcut;
}
oldtopcut=newtopcut%10007;
oldtop=newtop%10007;
}
return (newtop+newtopcut)%10007;
}
}//처음 삼각형은 4아니면3
//2번쨰 삼각형은? 14 11 8
// 다음 삼각형이 봉우리가 있을때 newtop = oldtop *3 + oldtopcut*2;
// 없을때 newtop = oldtop *2 + oldtopcut;
not null