10101 [BOJ] #1010 다리놓기 시간 제한 메모리 제한 정답 비율 2 초 128 MB 47.942% 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 방법 'dp[i][j]는 서쪽에 i 개의 점이 있고, 동쪽에 j 개의 점이 있다고 했을 때 놓을 수 있는 다리의 수' 라고 정의를 해보았다.그리고 그림을 그려봤는데, 같은 i개의 점일 때는 j값에 따라 같은 모습의 다리들이 반복되는 것을 볼 수 있었고 왼쪽 상단에 보이듯이 표를 채워보니 아래와 같은 규칙을 찾아낼 수 있었다. 그래서 식을 세워보면 이렇게 된다. i == 1 dp[i][j] = j.. 2019. 10. 2. 이전 1 다음