새소식

PS/백준

[백준/1328] 고층 빌딩 (Python)

  • -

Problem : https://www.acmicpc.net/problem/1328

 

1328번: 고층 빌딩

상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼

www.acmicpc.net

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:08:25

 


 

문제 설명

 

더보기

 

상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다.

상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤 순서로 위치해있는지는 알 수가 없다.

빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어졌을 때, 가능한 빌딩 순서의 경우의 수를 구하는 프로그램을 작성하시오.

예를 들어, N = 5, L = 3, R = 2인 경우에 가능한 빌딩의 배치 중 하나는 1 3 5 2 4이다.

 

 

입력 및 출력

 

더보기

입력

 

첫째 줄에 빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어진다.

 

출력

 

첫째 줄에 가능한 빌딩 순서의 경우의 수를 1000000007로 나눈 나머지를 출력한다.

 

입력 예시

 

3 2 2

 

출력 예시

 

2

 

 


 

풀이

 

발상의 전환이 필요한 DP. DP를 잘 활용할 수 있느냐는 둘째치고, 이 발상을 어떻게 적용시킬까에 대한 고민 역시 필요하다.

 

총 n개의 빌딩이 좌측으로는 l개, 우측으로는 r개가 보인다고 가정하자. 보통은 n+1번째 빌딩을 추가할 때 '더 큰 빌딩'을 추가하려고 생각해 보겠지만, 우리는 '가장 작은'빌딩을 추가한다고 역으로 생각해 볼 수도 있을 것이다.

 

가장 작은 빌딩이 들어갈 수 있는 경우는 총 (n+1)가지 경우가 있겠다. 제일 왼쪽에 들어가는 경우는 (n+1, l+1, r), 제일 오른쪽에 들어가는 경우는 (n+1, l, r+1), 그 외의 경우는 (n+1, l, r)이 된다. 이런 식으로 bottom-up으로 dp를 업데이트하도록 하면, 마지막에 (N, L, R)인 경우를 구할 수 있겠다.

 

 

풀이 코드

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

dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
dp[1][1][1] = 1

for i in range(1, N) :
  for j in range(1, i+1) :
    for k in range(1, i+1) :
      if not dp[i][j][k] :
        continue
      dp[i+1][j+1][k] += dp[i][j][k]
      dp[i+1][j][k+1] += dp[i][j][k]
      dp[i+1][j][k] += dp[i][j][k] * (i-1)

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

풀이 완료!

'PS > 백준' 카테고리의 다른 글

[백준/16287] Parcel (Python)  (1) 2023.10.31
[백준/1634] 완전 이진트리 (Python)  (1) 2023.10.30
[백준/1280] 나무 심기 (Python)  (1) 2023.10.28
[백준/1275] 커피숍2 (Python)  (1) 2023.10.27
[백준/1493] 박스 채우기 (Python)  (1) 2023.10.26
Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.