백준 1915 가장 큰 정사각형 혼내주기
스코페 3번 문제와 유사한데 크기가 1000이다. 무식하게 풀면 시간 초과에 걸린다. 주어진 위치에서 가장 큰 정사각형의 한 변 길이를 저장하는 dp table을 만들면 된다. 아래의 그림에서 파랑색 점의 현재 위치를 [x][y]라고 할 때, [x-1][y-1], [x-1][y], [x][y-1]의 최솟값 + 1이 [x][y]의 값이 된다. 만약 이 문제가 스코페에 나왔다면 풀지 못했을 것 같다... 갈 길이 멀다..... #include #include #include using namespace std; int map[1001][1001]; int main(){ ios::sync_with_stdio(0); cin.tie(0); string s; int n, m; cin >> n >> m; for(in..
혼내주기
2021. 8. 1. 23:26