문제설명 :
한 변의 길이가 1인 정삼각형 2n+1개를 이어붙여 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴을 만들 수 있습니다. 이때 사다리꼴의 윗변과 변을 공유하는 n개의 정삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙여 새로운 모양을 만들었습니다. 예를 들어 n이 4이고, 1번째, 2번째, 4번째 정삼각형 위에 정삼각형을 붙인 모양은 다음과 같습니다.
이렇게 만든 모양을 정삼각형 타일 또는 정삼각형 2개를 이어 붙인 마름모 타일로 빈 곳이 없도록 채우려고 합니다. 정삼각형 타일과 마름모 타일은 돌려서 사용할 수 있습니다.
타일을 놓을 때 다른 타일과 겹치거나 모양을 벗어나게 놓을 수는 없습니다. 위의 예시 모양을 채우는 방법 중 일부는 다음과 같습니다.
사다리꼴의 윗변의 길이를 나타내는 정수 n과 사다리꼴 윗변에 붙인 정삼각형을 나타내는 1차원 정수 배열 tops가 매개변수로 주어집니다. 이때 문제 설명에 따라 만든 모양을 정삼각형 또는 마름모 타일로 빈 곳이 없도록 채우는 경우의 수를 10007로 나눈 나머지를 return 하도록 solution 함수를 완성해 주세요.
풀이:
카카오 3LV 3개중에 가장 맘에 들어서 이걸 골랐다.
dp문제인거는 확실했는데 1차원인지 2차원인지 구분이 안 갔다.
처음 시도한 dp는 2차원배열로 1일때 0 일때를 나눠서 최댓값을 저장해놓고 해 두는 식이였다.
두 번째 dp는 1차원 배열로 썼다.
풀이:
def solution(n, tops):
dp = [0] * ((2 * n) + 1)
dp[0] = 1
if tops[0]:
dp[1] = 3
else:
dp[1] = 2
for i in range(2, 2 * n + 1):
# 위에 타일 놓는 곳 + 둬야하는곳
if i % 2 == 1 and tops[i // 2] == 1:
dp[i] = (dp[i - 1] * 2 + dp[i - 2]) % 10007
else:
dp[i] = (dp[i - 1] + dp[i - 2]) % 10007
print(dp[-1])
이번 풀이는 tops를 기준으로 한게 아니다
한 변 한 변 다 체크하기로했다.
dp[0] = 1 이다. 삼각형 한개 밖에 둘 수 없으니
dp[1] 은 3개혹은 2개이다.
3개인 경우는 tops[0] = 1일때 위에 삼각형이 올라가기때문에
만약에 tops[0] = 1일경우에는 3이고 아닐경우에는 삼각형2개로만들기, 마름모1개로 만들기 밖에 안돼서 두 개 이다.
dp[3] 도 마찬가지로
tops[0] = 1일 경우, 아닐경우로 나눈다.
있는 경우에는 4 없는 경우에는 3이다.
규칙을 발견하게 되는데. 홀수 인덱스 일때 , tops에 올릴지 말지 알 수 있다.
만약 안 올리게 된다면 단순하게 dp[i-2] + dp[i-1] 이 된다.
하지만 올리게 된다면 dp[i-1]*2 + dp[i-2] 인데.
그 이유는 위에 삼각형이 하나 더 올라오면서,
dp[i-1] 에서 삼각형 2개로 만드는경우와, 마름모 한개로 올리는경우가 생기기때문에 *2 를 해준다.
댓글