문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/258705
파이썬 소스: https://bit.ly/4b8Gquj이 문제를 보면, 정삼각형 1개의 오른쪽에 계속 붙여 나가는 문제입니다.
이 때, 붙이는 종류가 2가지 입니다. 정삼각형 3개를 붙일 수도 있고, 정삼각형 2개를 붙일 수도 있습니다.
이런 문제를 풀 때는, 문제에서 요구하는 것을 한번에 해결하기 보다는 문제를 조금 간소화 시켜서 풀어본 뒤에, 전체 문제를 푸는 것을 추천드립니다.
이 문제에서는 정삼각형 2개 or 3개를 붙일 수 있기 때문에, 간소화 시킨 문제는 정삼각형 2개만을 붙인다고 생각해 보는 것입니다.
그러면 첫 시작은 정삼각형을 4개 붙여 놓은 아래 모양입니다. 바로 n = 0 일 때 라고 할 수 있습니다.
정삼각형과 사다리꼴을 사용해서 채우는 방법은 모두 3가지로 아래와 같습니다.
이것만 가지고는 문제를 푸는 힌트를 얻기가 어렵습니다.
삼각형 2개를 더 붙였을 때, 정삼각형과 사다리꼴을 사용해서 채우는 방법을 알아 보겠습니다.
전체 8가지 경우로 아래와 같습니다. n = 1 일 때 라고 할 수 있습니다.
이제 n = 0인 경우와 n = 1인 경우를 비교 하여, 점화식을 만들어야 이 문제를 풀 수 있습니다.
2개의 그룹으로 나눠서 n=0 3가지경우와, n=1 8가지 경우의 관련성을 알아보겠습니다.
우선 아래 f, g, h 는 \ 모양의 마름모로 끝나는 경우입니다. 모두 n=0 의 경우에 \ 모양의 마름모를 붙였 다는 것을 알 수 있습니다.
여기서 n=1 일 때, \ 마름모 끝나는 경우는 n=0 일 때 모든 경우의 수의 합과 같다는 것을 알 수 있습니다.
2차원 배열 dp를 선언하고, row값이 n, column 값이 1이 \ 마름모로 끝나는 경우라고 정의 한다면, 아래와 같이 점화식의 일부를 완성할 수 있습니다.
dp[n][1] = n-1 번째의 모든 경우의 수의 함
이와는 반대로, \ 마름모로 끝나지 않는 모든 경우, 즉 / 마름모로 끝나거나, 삼각형으로 끝나는 경우를 모아 보면 아래와 같습니다.
a 는 왼쪽 n=0 모양에서, 삼각형으로 채운 경우 입니다.
b 는 왼쪽 n=0 모양에서, / 마름모로 채운 경우 입니다.
c 는 왼쪽 n=0 모양에서, 삼각형으로 채운 경우 입니다.
d 는 왼쪽 n=0 모양에서, / 마름모로 채운 경우 입니다.
e 는 왼쪽 n=0 모양에서, \ 마름모로 끝나서, 삼각형으로 채운 경우입니다.
\ 마름모로 끝나지 않는 모든 경우, 즉 / 마름모로 끝나거나, 삼각형으로 끝나는 경우를 dp[n][0] 으로 정의 한다면 아래와 같이 점화식을 작성할 수 있습니다.
dp[1][0] = dp[0][0] * 2 + dp[0][1]
dp[n][0] 은 ‘\ 마름모로 끝나지 않는 모든 경우, 즉 / 마름모로 끝나거나, 삼각형으로 끝나는 경우’ 로 정의 하고, dp[n][1] 은 ‘\ 마름모로 끝나는 경우’ 로 정의 하였으므로, dp[n][0] dp[n][1]의 점화식은 아래와 같습니다.
dp[n][0] = dp[n-1][0] * 2 + dp[n-1][1]
dp[n][1] = dp[n-1][0] + dp[n-1][1]
위의 점화식을 사용해서 입출력 예#3 번을 풀어 보려면, dp[0]의 값을 아래와 같이 셋팅합니다.
dp: List[List[int]] = [[0, 0] for _ in range(n)]
MOD = 10007
dp[0][0] = 2
dp[0][1] = 1
for idx in range(1, n):
dp[idx][0] = dp[idx - 1][0] * 2 + dp[idx - 1][1]
dp[idx][1] = dp[idx - 1][0] + dp[idx - 1][1]
dp[idx][0] %= MOD
dp[idx][1] %= MOD
range()함수의 인자가, 1, n 인 것을 확인해주시구요, 매번 MOD 값의 나머지를 저장하는 해야 합니다. 뒤로 갈 수록 큰 숫자가 나오기 때문에, 매전 MOD 값의 나머지를 계산하지 않으면, 잘 못 된 결과를 얻을 수 있습니다.
이렇게 코딩한 후에, 마지막에 리턴한 answer 값은 아래와 같이 계산합니다.
answer = (dp[n - 1][0] + dp[n - 1][1]) % MOD
여기서도 마찬가지로, MOD 값의 나머지를 계산합니다. 이렇게 문제를 풀면 입출력 예#3
의 답 7704를 얻을 수 있습니다.
이제 tops[n] 이 0인 경우의 정답은 찾을 수 있으니, tops[n] 이 1인 경우를 고려해 보겠습니다.
tops[0] 이 1이라면, dp[0] 초기값도 달라지게 됩니다.
if tops[0] == 1:
dp[0][0] = 3
dp[0][1] = 1
else:
dp[0][0] = 2
dp[0][1] = 1
dp[0][0] 은 3이 됩니다. / 마름모, 삼각형으로 채우는 경우 이외에, 윗쪽으로 향하는 마름모 경우의 수가 생겼기 때문에 1증가한 3이 됩니다.
dp[idx][0] = dp[idx - 1][0] * 3 + dp[idx - 1][1] * 2
**dp[idx - 1][0]**을 계산하는 방식도 곱하기 2에서 곱하기 3으로 1 증가 합니다. 윗쪽으로 향하는 마름모의 경우의 수를 고려해서, 2에서 1증가한 3이 됩니다.
dp[idx - 1][1] 즉, 직전 단계에서 \ 마름모로 끝난 경우도, 곱하기 2를 해야 합니다. \마름모로 끝날 수도 있고, 윗쪽으로 향하는 마름모로 끝날 수도 있기 때문입니다.
댓글 없음:
댓글 쓰기