11726번 - 2*N 타일링

---

분석

이런 문제입니다.

2xn이라는 총 공간이 주어졌을 때 1x2타일과 2x1타일을 이용해서 이 공간을 채울 수 있는 경우의 수를 구하면 되는 문제입니다.

이런 경우 두 가지 유형으로 나눌 수 있는데
먼저 타일이 1x2타일로 끝나는 경우 와 타일이 2x1 타일로 끝나는 경우입니다.
따라서 점화식은 DP(N) = DP(N-1) + DP(N-2)라는 형태로 작성할 수 있습니다.

---

코딩

N = int(input())
print(dp(N)%10007)

입력을 받고 큰값이 나오니까 해를 10007로 나누라 했으므로 문제대로 따라줍니다.

memo = [0] * 1001
def dp(n):
    if n == 1:
        return 1
    if n == 2:
        return 2

최대 값이 1000이므로 메모이제이션 크기는 1001로 설정해주겠습니다.
1인 경우 1가지 경우밖에 안되므로 1 return, 2인경우 2가지 경우밖에 안되므로 2 return 하고

    if memo[n]:
        return memo[n]

메모이제이션에 데이터가 존재할 경우 해당 데이터를 return

    memo[n] = dp(n-1) + dp(n-2)
    return memo[n]

아까 도출한 점화식을 return 해주면 최종적으로 DP를 활용해 문제풀이가 가능합니다.

---

---

11727번 - 2*N 타일링 2

위 문제를 응용한 문제입니다.
이번엔 2x2 타일이 하나 추가됬네요.
초기값하고 점화식만 조금 바꿔주면 될듯 싶습니다.

N = int(input())
print(dp(N)%10007)

N을 입력받고

memo = [0] * 1001
def dp(n):
    if n == 1:
        return 1
    if n == 2:
        return 3

길이가 2일때 2x2타일 하나, 1x2타일 2번, 2x1타일 2번 총 3번으로 만들수 있기 때문에 3으로 초기화를 진행해줍시다.

    if memo[n]:
        return memo[n]
    memo[n] = dp(n-1) + dp(n-2) + dp(n-2)
    return memo[n]

그리고 마지막 부분에 2x2타일도 올 수 있으므로 dp(n-2)를 하나 더 추가하면 정답을 도출할 수 있습니다.

---

2133번 - 타일 채우기

타일 채우기 끝판왕 문제입니다.
이번에는 크기가 3xN인 벽을 1x2, 2x1 타일로 채우는 방법을 계산해야 합니다.

---

분석

1. 타일 값 선언

타일을 채우기 시작하는 부분(초기화값)부터 한번 살펴보겠습니다.
일단 공간이 1인 경우에는 타일을 세워서 공간을 못만듭니다!
그리고 공간이 2인 경우에는

이렇게 3개의 경우로 스타트를 끊을 수 있겠습니다.
그리고 제가 하나 간과했던 점이 있는데 GPT한테 물어보니 명쾌한 해답을 내놓더군요.

그건 바로 공간이 0인 경우도 하나의 경우의 수로 취급되어 1로 스타트를 끊을 수 있다는 겁니다!
이제 이걸 코드로 표현하면

    if n == 0:
        return 1
    if n == 1:
        return 0
    if n == 2:
        return 3

이런 느낌으로 초기값을 선언하고 시작할 수 있습니다.

2. 타일을 끝맺을 때 경우의 수

이게 좀 복잡합니다.
일단 위의 예시처럼 2칸만 남았을 때는 3 X DP(N-2) 값으로 점화식을 세우는 게 가능합니다.

그런데 이제 제가 그려둔 오른쪽 예시를 보시면 2XDP(N-짝수) 만큼 계속해서 점화식을 세우는 게 가능하여 결과적으로 N-i가 0이 될때까지 점화식을 세우는 게 가능해집니다...

For문을 사용하여 N-i가 0이 될때까지 점화식을 세우고 메모이제이션에 추가해주는 방식으로 코딩해야 문제풀이가 가능하겠습니다.

---

코딩

N = int(input())
print(dp(N))

N 입력을 받아주고 dp(N)을 실행시켜줍니다.

memo = [0] * 1001
def dp(n):  
    tmp = 0

    if n == 0:
        return 1
    if n == 1:
        return 0
    if n == 2:
        return 3

메모이제이션을 하나 만들어주고 위에 분석처럼 시작 크기에 알맞게 return 값을 대입해줍시다.

    if memo[n]:
        return memo[n]

메모이제이션에 있는 값이면 해당 메모로 값을 return 해주고

    tmp = 3 * dp(n-2)

없는 값이면 일단 2칸 남았을 경우의 점화식을 세우고 해당 값을 tmp에 추가시키겠습니다.

    for i in range(3,n+1):
        if i%2 == 0:
            memo[n] += 2 * dp(n-i)

핵심 부분입니다.

4칸 이상의 짝수칸이 남았을 경우에는 2 X DP( N - 반복문변수)라는 점화식을 0이 되기 전까지 계속해서 돌려줍니다.

해당 부분은 4칸,6칸,8칸...계속해서 N 전까지 경우의 수가 늘어날 여지가 있기 때문에 for문안에 점화식을 넣어 처리해주도록 합시다.

    return memo[n]

마지막으로 return 메모이제이션을 하면 정답을 도출할 수 있습니다.

---

---