[프로그래머스] 산 모양 타일링

문제

프로그래머스

 

입력

n:Int = 윗변의 길이
tops:[Int] = 정삼각형의 위쪽에 정삼각형을 붙이는 여부

tops[i] = 0  없는 경우
tops[i] = 1  위에 삼각형이 있는 경우

결과

ans: Int = 만들 수 있는 경우의 수를 10007로 나눈 결과

놓을 수 있는 경우의 수

해석

 

보자마자 dp를 의심할 수 있다. 왜냐하면 이전 삼각형 상태로 다음 상황이 결정되기 때문에 부분 문제를 풀어야되는 dp카테고리다.

 

경우의 수를 생가가해보지.

 

 

1. 현재 i-1에 2번이 놓여있을 때

• i에 1,3,4(위에 공간이 있을 때) 놓을 수 있음 

2. 현재 i-1에 3번이 놓여있을 때

• i에 1,4(위에 공간이 있을 때) 놓을 수 있음

즉, 현재 i 번째에 위에 삼각형을 놓을 수 있는, 즉 tops[i] = 1 라면 4번이 가능하고 그렇지 않으면  그 나머지만 가능하다.

 

현재 i에 2번 사각형을 놓을려 할 때  경우의 수

1. tops[i] = 1 
- dp[i-1]에 2번을 놓았을 때 *3 + dp[i-1]에 3번을 놓았을 때 * 2 

2. tops[i] = 0  
- 4번 만 싹 빼면
-  dp[i-1]에 2번을 놓았을 때 *2 + dp[i-1]에 3번을 놓았을 때 * 1

 

그렇다면 i번째에 3번을 놓을려면 ?? 따로 앞에서 제약받는게 없다 이전 상황의 경우의 수를 그대로 이어 받는다.

dp[i+1] = dp[i]에 2번을 놓았을 때 + dp[i]에 3번을 놓았을 때 

 

정리하면 

 

dp[i][0] = i 번째 윗변에 왼쪽 사다리꼴을 쓸 경우 , dp[i][1] = i 번째 오른쪽 사다리꼴 쓸경우

1. 왼쪽 고려
a. 위에 놓을 수 있을 때
dp[i+1][0] = dp[i][0]*3 + dp[i][1]*2

b. 놓을 수 없을 때

2. 오른쪽 고려
dp[i+1][1] = (dp[i][0] + dp[i][1])

코드

import Foundation

func solution(_ n:Int, _ tops:[Int]) -> Int {
    
    let DIV: Int = 10007
    
    var dp: [[Int]] = [[Int]](repeating:[0,0],count:n+1) // dp[i][0] = i 번째 윗변에 왼쪽 사다리꼴을 쓸 경우 , dp[i][1] = i 번째 오른쪽 사다리꼴 쓸경우 
    
    dp[0][0] = 1 // 
    
    for i in 0..<n {
        
        if tops[i] == 1 { // 세로형을 사용할 수 있음 
            
            //i+1에 왼쪽꺼를 놓을려면 , i번째는 오른쪽 거를 놓으면 안됨
            
            // dp[i][0] = (오른쪽 꺼 사용불가)  왼쪽형 ,세로형 , 그냥 정삼각형 = 3 
            
            // dp[i][1] = (왼쪽꺼 사용 불가)  정삼각형, 세로 = 2
        
            dp[i+1][0] = dp[i][0]*3 + dp[i][1]*2 
        }
        
        else { // 세로형 사용 불가 , 위와 똑같지만 세로형 만 빼야됨
            
            dp[i+1][0] = dp[i][0]*2 + dp[i][1]*1
        }
        
         //i+1에 오른쪽 껄 놓을 때는 i번째가 왼쪽이든 오른쪽이든 상관 없음
        dp[i+1][1] = (dp[i][0] + dp[i][1]) % DIV
        
        dp[i+1][0] %= DIV 
        
       
        
        
    }

    
    return (dp[n][1] + dp[n][0]) % DIV
}