반응형
https://www.acmicpc.net/problem/14925
14925번: 목장 건설하기
랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하
www.acmicpc.net
[ 문제풀이 ]
1. dp[ 1001 ][ 1001 ] 배열을 선언하고, arr 배열에 땅을 입력받아 저장합니다.
2. 이중 for문을 이용하여 arr[ i ][ j ] 를 돌면서 arr[ i ][ j ] == 0일 때, 다음의 점화식을 이용하여 답을 구해줍니다.
dp[ i ][ j ] = min(dp[ i - 1 ][ j ], min(dp[ i ][ j - 1 ], dp[ i - 1 ][ j - 1 ])) + 1
3. ans = max(ans, dp[ i ][ j ])를 통해 ans를 구해 출력합니다.
[ 소스코드 ]
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 | #include<iostream> using namespace std; int M, N; int arr[1001][1001]; int dp[1001][1001]; int ans; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> M >> N; for (int i = 1; i <= M; i++) { for (int j = 1; j <= N; j++) { cin >> arr[i][j]; } } for (int i = 1; i <= M; i++) { for (int j = 1; j <= N; j++) { if (arr[i][j] == 0) { dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i-1][j-1])) + 1; ans = max(ans, dp[i][j]); } } } cout << ans; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 9177번 - 단어 섞기 (C++) (0) | 2023.09.29 |
|---|---|
| [ 백준 ] 1351번 - 무한 수열 (C++) (0) | 2023.09.28 |
| [ 백준 ] 20924번 - 트리의 기둥과 가지 (C++) (0) | 2023.09.26 |
| [ 백준 ] 10835번 - 카드게임 (C++) (0) | 2023.09.25 |
| [ 백준 ] 3197번 - 백조의 호수 (C++) (0) | 2023.09.24 |