문제 :
1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
예를 들어
1234
0 | 1 | 1 | 1 |
1 | 1 | 1 | 1 |
1 | 1 | 1 | 1 |
0 | 0 | 1 | 0 |
가 있다면 가장 큰 정사각형은
1234
0 | 1 | 1 | 1 |
1 | 1 | 1 | 1 |
1 | 1 | 1 | 1 |
0 | 0 | 1 | 0 |
가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.
제한사항 :
- 표(board)는 2차원 배열로 주어집니다.
- 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
- 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
- 표(board)의 값은 1또는 0으로만 이루어져 있습니다.
입출력 예 :
board | answer |
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] | 9 |
[[0,0,1,1],[1,1,1,1]] | 4 |
방법 :
* 동적계획법 (DP:Dynamic Programming)를 이용해서 푼다.
노랑색 칸의 좌측, 상단, 좌측상단 값 중에서 최솟값을 골라 +1해주면 노랑색 칸이 된다.
위 그림에서 나올 수 있는 최대 정사각형의 한 변의 길이는 1이다.
1. board[1][1]부터 시작을 해서 board의 값이 1인지 확인을 한다.
(왜 board[1][1]부터 인가? 좌측,상단,좌측상단이 없기 때문이다.)
2. 값이 1이면 좌측,상단,좌측상단 값 중에서 최솟값을 골라서 1을 더해준다.
3. 현재 board에 최솟값+1을 갱신하고 기존의 최대 변의 길이와 비교하여 변의 길이의 최댓값도 갱신해준다.
코드 :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> board)
{
int answer = board[0][0];
for(int i = 1; i < board.size(); i++){
for(int j = 1; j < board[0].size(); j++){
if(board[i][j]){
board[i][j] = min(board[i][j - 1], board[i - 1][j]);
board[i][j] = min(board[i - 1][j - 1], board[i][j]) + 1;
answer = max(answer, board[i][j]);
}
}
}
return answer * answer;
}
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스/level2/c++] 더 맵게 (0) | 2021.01.25 |
---|---|
[프로그래머스/level2/c++] 가장 큰 수 (0) | 2021.01.24 |
[프로그래머스/level2/c++] 프린터 - "스택/큐" (0) | 2021.01.24 |
[프로그래머스/level2/c++] 주식 가격 - "스택/큐" (0) | 2021.01.24 |
[프로그래머스/level2/c++] 전화번호 목록 - "해시" (0) | 2021.01.23 |