반응형
https://www.acmicpc.net/problem/1577
1577번: 도로의 개수
첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자
www.acmicpc.net
[ 문제풀이 ]
1. 먼저 공사 중인 도로를 체크하기 위해 broke [205][205] 배열을 선언하고, 공사 중인 도로일 경우 broke [ b + d ][ a + c ] = 1로 갱신해 줍니다.
2. arr[ i ][ j ] = arr [ i - 1 ][ j ] + arr [ i ][ j - 1 ]의 점화식을 이용하여 문제를 풀어줍니다.
3. 2의 순서에서 공사 중인 도로가 있다면 더해주지 않습니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include<iostream> #include<map> using namespace std; int N, M; long long arr[101][101]; int dy[2] = { -1,0 }; int dx[2] = { 0,-1 }; int broke[205][205]; //공사 중인 도로 체크 int main() { arr[0][0] = 1; scanf("%d %d", &N, &M); int num; scanf("%d", &num); for (int i = 0; i < num; i++) { int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d); broke[b + d][a + c] = 1; } for (int i = 0; i <= M; i++) { for (int j = 0; j <= N; j++) { for (int k = 0; k < 2; k++) { int yy = i + dy[k]; int xx = j + dx[k]; if (yy >= 0 && yy <= M && xx >= 0 && xx <= N) { if (broke[yy+i][xx+j] != 1) { arr[i][j] += arr[yy][xx]; } } } } } printf("%lld", arr[M][N]); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2253번 - 점프 (C++) (0) | 2022.11.06 |
|---|---|
| [ 백준 ] 14002번 - 가장 긴 증가하는 부분 수열 4 (C++) (0) | 2022.11.05 |
| [ 백준 ] 2229번 - 조 짜기 (C++) (0) | 2022.11.03 |
| [ 백준 ] 2157번 - 여행 (C++) (0) | 2022.11.02 |
| [ 백준 ] 2666번 - 벽장문의 이동 (C++) (0) | 2022.11.01 |