[백준] 1328번 고층빌딩 DP ( python )

 

 

 

인생 처음으로 푸는 플레 문제이다. 

 

DP 문제를 풀면서 느끼는 건데 뭔가 이 알고리즘에 대해 깨달았다.

 

이 문제 푸는데도 그렇게 엄청 어렵다 정도는 아니었다.

 

 

( 패드가 방전되어서 오랜만에 빡지로 풀어보기.. )

 

 

꽤 간단했다.

 

문제 설명 )

 

작은 빌딩을 설치해야 하는 상황이다.

 

자 우리가 건물을 바라볼 때 큰 건물 뒤에 작은 건물이 있다면 과연 그 건물이 보일까?

 

이 문제가 그런 방식으로 접근을 하는 것!!

 

어찌 됐든 작은 빌딩이 양쪽 맨 끝에 두었을 때 보일까? 제일 처음에 있는 빌딩이라 무조건 보인다.

 

그래서 +1이 된다.

 

그럼 많고 많은 빌딩 사이에 작은 빌딩이 낀다면? 보이지 않을 것이다.

 

자 문제의 규칙성을 찾아냈다.

 

그럼 결론적으로 점화식은?

 

dp [N][L][R] = dp [N-1][L-1][R] + dp [N-1][L][R-1] + (dp [N-1][L][R]*(N-2))

 

왼쪽에 설치한 경우 + 오른쪽에 설치한 경우 + 가운데에 배치한 경우

 

 

맞은 코드

N, L, R = map(int, input().split())

dp = []
for n in range(N + 1):
    layer = []
    for l in range(L + 1):
        row = [0] * (R + 1)
        layer.append(row)
    dp.append(layer)

dp[1][1][1] = 1

for n in range(2, N + 1):
    for l in range(1, L + 1):
        for r in range(1, R + 1):
            dp[n][l][r] += dp[n - 1][l - 1][r]
            dp[n][l][r] += dp[n - 1][l][r - 1]
            dp[n][l][r] += dp[n - 1][l][r] * (n - 2)
            dp[n][l][r] %= 1000000007

print(dp[N][L][R])

 

 

 

 

---

 

이 문제를 풀면서 뭔가 자신감이 더 오르게 된 계기가 된 거 같다.

 

진짜 거짓말 안치고 1년 전만 해도 알고리즘 사용도 못해서 쩔쩔매고 언어를 사용해서 문제를 풀려해도 힘들고 구현 문제도 풀지 못했는데

 

이제는 언어가 몸에 익어서 생각을 어떻게 더 잘하냐가 중요한 과제가 된 거 같다.