반응형

문제 출처 :


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