알고리즘 문제
[C/C++ 백준 1010번] 다리 놓기 (Silver 5)
새파란 공대생
2020. 5. 15. 18:49
https://www.acmicpc.net/problem/1010
1010번: 다리 놓기
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.
www.acmicpc.net
계속 풀면서 느끼는건데, 낮은 등급 문제라도 하나씩 풀어가는게 더 좋은것 같다. 무시할 이유가 없다.
이 문제는 dp[left][right]로, left를 왼쪽 사이트의 개수, right를 오른쪽 사이트의 개수라고 하고 dp를 구하면 된다.
항상 그렇듯이 점화식을 세워야하는데, right에 사이트가 하나 들어왔다고 생각시
① 그 사이트를 안쓸 경우 -- dp[i][j] += dp[i][j-1]
② 쓸 경우, left의 가장 아래의 사이트와 연결해야만 한다. 안그러면 다리 짓기 불가능 -- dp[i][j] += dp[i-1][j-1]
그리고 예외사항 하나만 처리해주면 되는데, i==1일 경우이다. 이 경우 dp[i][j]=j;
#include <cstdio>
int main(void){
int T, left, right, dp[31][31]={0,};
for(int i=1; i<31; i++){
for(int j=1; j<31; j++){
if(i>j) dp[i][j]=0;
else if(i==1) dp[i][j]=j;
else{
dp[i][j]=dp[i][j-1]+dp[i-1][j-1];
}
}
}
scanf("%d", &T);
for(int i=0; i<T; i++){
scanf("%d %d",&left, &right);
printf("%d\n",dp[left][right]);
}
}