다리 놓기 (실버 5)

다리 놓기 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

128 MB

91576

42770

34804

48.045%

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

---

 

 

문제 접근

 

전형적인 DP 문제이다. 작은 해결에서 큰 해결책을 찾는 DP를 다시 상기해 보며 문제를 풀었다.

아무 참고 자료 없이 풀었던 점에서, 확실하게 DP에 대한 복습 하는 시간이 되었다.

 

 

최대한 다리를 그려가며 특정한 조건을 최대한 찾아내었다.

 

1.  N 의 값이 1일 때는 무조건 경우의 수가 M이 되는 것

2.  N == M 일 경우 경우의 수가 무조건 1

3. N < M 일 경우 특정한 패턴을 찾기 위해 손으로 직접 그려가며 문제에 접근하였다.

 

 

 

이때 이전 까지의 사이트에 대한 경우의 수가 저장되어 있다면? 쉽게 문제가 풀릴 것이다.

 

1번 2번 케이스와 다른 가장 작은 경우의 수인 N = 2 , M = 3 일 경우를 생각해 보았다.

 

다리를 교차하여 건설할 수 없음으로 N의 맨 위의 사이트를 정하고 나면 아래의 사이트의 경우의 수를 구하면 된다.

 

따라서 이전 작은 경우의 수를 활용하는 DP의 특성을 파악하여 DP 테이블을 그려 점화식을 정리하였다.

 

 

1,2번 케이스의 경우를 먼저 채워 넣어 준다.

 

베이스가 되는 경우의 수를 채워 넣어야 내가 구할 수 있는 것을 계산할 수 있기 때문에 

 

DP테이블을 그릴 때 가장 먼저 초기화를 시켜준다.

 

dp 테이블을 직접 채워가는 과정

 

작은 케이스에서 생각해낸 로직을 쉽게 DP 테이블에서 패턴을 확인할 수 있었다. 

 

dp [2][2]를 구하기 위해 이전 요소를 활용하여 풀어주었다.

 

이를 일반화하면 다음과 같은 식이 된다.

 

 

코드 구현 

 

좋다 이제 코드를 구현하면 된다. 

 

dp 테이블의 일반식을 구했다면 구현하는 것은 일도 아니다. 

 

문제의 요구조건에 맞게 while 문과 for문을 이용하여 dp 테이블을 채워주는 로직을 구현하였다.

 

 

전체 소스 코드

# 1월 4일 DP 다리 놓기

# 실버5

# dp table bottom up 방식

T = int(input())

while T > 0:
  N, M = map(int,input().split())
  
  T -= 1

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

  for i in range(M):
    dp[0][i] = i+1

  for i in range(1,N):
    for j in range(1,M):
      if i == j:
        dp[i][j] = 1
      elif i > j:
        dp[i][j] = 0
      elif i < j:
        dp[i][j] = dp[i][j-1] + dp[i-1][j-1]

  print(dp[-1][-1])

 

채점 결과

 

피드백

DP 다이나믹 프로그래밍의 기초가 되는 좋은 문제였다고 생각한다. dp 테이블을 채우는 bottom-up 방식보다 재귀 함수를 이용한 top down 방식의 풀이도 도전해보며 다양한 접근을 시도하는 것 또한 해야겠다고 생각한다.