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

comomo·2024년 5월 27일

코딩연습

목록 보기

28/28

문제

Lv.3 산 모양 타일링

문제설명

한 변의 길이가 1인 정삼각형 2n+1개를 이어붙여 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴을 만들 수 있습니다. 이때 사다리꼴의 윗변과 변을 공유하는 n개의 정삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙여 새로운 모양을 만들었습니다. 예를 들어 n이 4이고, 1번째, 2번째, 4번째 정삼각형 위에 정삼각형을 붙인 모양은 다음과 같습니다.

이렇게 만든 모양을 정삼각형 타일 또는 정삼각형 2개를 이어 붙인 마름모 타일로 빈 곳이 없도록 채우려고 합니다. 정삼각형 타일과 마름모 타일은 돌려서 사용할 수 있습니다.

타일을 놓을 때 다른 타일과 겹치거나 모양을 벗어나게 놓을 수는 없습니다. 위의 예시 모양을 채우는 방법 중 일부는 다음과 같습니다.

사다리꼴의 윗변의 길이를 나타내는 정수 n과 사다리꼴 윗변에 붙인 정삼각형을 나타내는 1차원 정수 배열 tops가 매개변수로 주어집니다. 이때 문제 설명에 따라 만든 모양을 정삼각형 또는 마름모 타일로 빈 곳이 없도록 채우는 경우의 수를 10007로 나눈 나머지를 return 하도록 solution 함수를 완성해 주세요.

제한사항

1 ≤ n ≤ 100,000
tops의 길이 = n
tops[i]는 사다리꼴의 윗변과 변을 공유하는 i+1번째 정삼각형의 위쪽에 정삼각형을 붙이는 경우 1, 붙이지 않는 경우 0입니다.

해결방법

위의 사진과 유사한 형태의 도형을 정삼각형이나 마름모를 이용하여 채우는 경우의 수를 10007로 나눈 나머지를 구하는 문제이다.

아이디어 1

먼저 생각한 방법은 위와 같은 모형에서 마름모가 들어갈 수 있는 최대 개수는 n개이기 때문에 마름모의 개수에 따른 가능한 경우의 수를 구하여 더하는 방식을 생각했었다.
0개와 1개의 마름모를 사용하는 경우는 각각 1,(2n+윗변의 정삼각형 개수)로 구하기 그리 어렵지 않았지만 2개 이상부터는 가능한 경우의 수를 식으로 나타내기 힘들어어서 이 방식은 사용하지 않았다.

아이디어 2
그 다음으로 생각하는 것은 수열처럼 모형을 나누고 길이를 1씩 증가시켜 가면서 길이가 증가할 때 경우의 수 사이의 점화식을 구하는 방법을 생각했다.

윗변의 개수를 기준으로 도형을 사다리꼴이나 큰 정삼각형으로 나누어서 경우의 수를 생각했다.
위와 같은 방식으로 나누었을때에 도형을 채울수 있는 방법은 각각 4개 ,3개 였다.
그러므로 앞에서 구한 경우의 수에 윗변에 삼각형이 있는지에 따라 4,3을 곱해주면 될것 같았지만 그럴 경우 아래사진과 같이 채우는 경우 때문에 값이 달라졌다.

그렇기에 다음 공간을 채우는데 영향을 주는 우하단 삼각형을 마름모로 채우는 경우와 채우지 않는 경우로 나누어서 생각을 해보았다.

채우지 않는 경우와 채우는 경우의 수를 각각 a,b라고 했다.
이렇게 나눈 경우 각 항마다 관계를 식으로 나타내는게 가능했다.

top[0]==1이면a[0]=3,b[0]=1
top[0]==0이면a[0]=2,b[0]=1

top[n]==1
a[n]=3a[n-1]+2b[n-1]
b[n]=a[n-1]+b[n-1]

top[n]==0
a[n]=2a[n-1]+b[n-1]
b[n]=a[n-1]+b[n-1]
위와 같은 식으로 표현이 가능했고 위의 식을 사용하여 코드를 작성하였다.

C++코드1

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> tops) {
    long *x=new long[n];
    long *y=new long[n];
    x[0]=tops[0]?3:2;
    y[0]=1;
    
    for(int i=1;i<n;i++)
    {
        if(tops[i]) x[i]=3*x[i-1]+2*y[i-1];
        else x[i]=2*x[i-1]+y[i-1];
        y[i]=x[i-1]+y[i-1];
        
        x[i]%=10007;
        y[i]%=10007;
    }
    
    return (x[n-1]+y[n-1])%10007;
}

코드1 같이 쓰면 테스트케이스 11정도부터 싹 다 틀린다.
설마 오버플로우인가 싶어서 파이썬으로 동일한 코드를 작성하여 실행해보니 통과가 되었다.

Python코드

def solution(n, tops):
    if tops[0]:
        x=3
    else:
        x=2
    y=1
    
    for i in range(1,n):
        
        if tops[i]:
            x,y=3*x+2*y,x+y
        else:
            x,y=2*x+y,x+y
            
    return (x+y)%10007

C++코드2

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> tops) {
    long *x=new long[n];
    long *y=new long[n];
    x[0]=tops[0]?3:2;
    y[0]=1;
    
    for(int i=1;i<n;i++)
    {
        if(tops[i]) x[i]=3*x[i-1]+2*y[i-1];
        else x[i]=2*x[i-1]+y[i-1];
        y[i]=x[i-1]+y[i-1];
        
        x[i]%=10007;
        y[i]%=10007;
    }
    
    return (x[n-1]+y[n-1])%10007;
}