MathTrauma

문제 링크 : https://www.acmicpc.net/problem/11495 11495번: 격자 0 만들기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각 www.acmicpc.net 1X2 혹은 2X1 타일로 덮는 문제처럼 생각하자. 이 타일들은 좌표 (i , j) 에 대해서 i+j 가 짝수인 것 하나과 홀수인 것 하나를 덮는다. (여기서는 타일들이 곂쳐지게 덮어도 된다.) i+j 가 짝수인 것(짝수 노드)들을 기준으로 타일들을 덮으면, i+j 가 홀수인 것(홀수 노드)들 중 하나가 얼떨결에 같이 덮힌다. 짝수 노드의 값을 1 줄이면..

문제 링크 : https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 각각의 i, j 에서 변의 길이 \( l \) 을 이용하여 loop 를 돌리면 시간 복잡도는 \( O(n^4) \) 이 된다. 2차원 부분합을 미리 구했다면 \(O(n^3)\) 으로 해결할 수 있지만 시간 초과일 것이다. 앞 단계에서 최대 정사각형을 찾기 위해 조사한 것을 재활용할 수 있음을 깨닫게 되면 DP 풀이는 쉽다. 우선 문자열 2차원 배열을 정수 2차원 배열 grid 에 저장했다고 가정한다. 그리고, dp[i][j] 를 i , j 가 정사각형의..