반응형
문제 출처 :
https://www.acmicpc.net/problem/1915
알고리즘 분석 :
문제 해결에 필요한 사항
1. Dynamic Programming
2. 점화식 세우는 방법
문제 해결 방법은 다음과 같다.
일단 입력은 scanf("%1d",~); 방식으로 숫자 하나씩 받아들이는 입력처리를 하면 되고,
점화식 과정은 현재 DP[i][j] 부분에서
DP[i-1][j] 부분을 봤을 때 현재까지 정사각형 누적 길이,
DP[i][j-1] 부분을 봤을 때 현재까지 정사각형 누적 길이,
DP[i-1][j-1] 부분을 봤을 때 현재가지 정사각형 누적 길이 중
최솟값을 구하면 된다.
max를 이용하게 될 시 범하는 오류는 다음과 같은 예제이다.
001
011
000
이 값이 답이 2가 나올 것이다.
이 DP를 구하는 전제는 대신 arr[i][j]가 0이 아닌 1일때 DP를 구할 수 있다.
소스 코드 :
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 | #include <iostream> #include <cstdio> #include <algorithm> using namespace std; int DP[1003][1003]; int arr[1003][1003]; int ans; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%1d", &arr[i][j]); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if(arr[i][j]) { DP[i][j] = min({ DP[i - 1][j], DP[i][j - 1], DP[i - 1][j - 1] }) + 1; ans = max(DP[i][j], ans); } cout << ans*ans; return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[9663번] N-Queen (0) | 2017.04.27 |
---|---|
[1377번] 버블 소트 (0) | 2017.04.27 |
[1213번] 팰린드롬 만들기 (0) | 2017.04.26 |
[1015번] 수열 정렬 (2) | 2017.04.25 |
[2038번] 골롱 수열 (2) | 2017.04.25 |