문제

보자마자 brute force로 풀면 될 것 같았는데 구현하다보니 for문을 다섯 번 중첩해서 쓰는 나를 발견했다..
채점 서버의 성능을 믿고 끝까지 나갔으나 O(n^5)인데 당연히 시간초과가 났음

내 주변 board들의 값에 의해 결정되는 거고 과거의 값들을 재활용(..)하니까 dp로 풀 수 있을까?라 생각했는데 구체적인 방법이 생각이 안났다. 그래서 결국 다른 사람의 설명으로부터 아이디어를 얻어 풀었다.

근데 아직 완전히 내꺼화된 것 같진 않다. 다음에 이 문제가 주어졌을 때 스스로 풀 수 있다 정도는 아닌 것 같다. 며칠 뒤에 다시 풀어봐야지 흑흑

실패한 코드

답은 정확하지만 효율성 0점 5중 for문인데 그럴 만 하다. 머리가 나쁘면 손가락이랑 컴퓨터가 고생한다 ㅠ.ㅠ ㅋㅋㅋㅋ

#include <iostream>
#include<vector>
using namespace std;

int solution(vector<vector<int>> board)
{
	int answer = 1234;
	int size = board.size();
	int i, j, k, l, m; // i: row start | j: col start | k: row | l: col | m: side

	for (m = size; m >= 1; m--) {
		// i, j는 정사각형의 왼쪽 위 좌표
		for (i = 0; i + m <= size; i++) {
			for (j = 0; j + m <= size; j++) {
				// k, l은 실제로 이동하면서 1로 이뤄져 있는지
				int cnt = 0;
				for (k = i; k < i + m; k++) {
					for (l = j; l < j + m; j++) {
						cnt += board[k][l];
					}
				}
				if (cnt == m * m) return cnt;
			}
		}
	}
	return answer;
}

timeout

테케랑 효율성 다 통과한 코드 (DP)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> board)
{
    int answer = board[0][0]; // 이렇게 하면 board가 한 줄일 때도 답을 구할 수 있다.
    int row = board.size();
    int col = board[0].size();
    int i, j;

    for(i = 1; i < row; i++) {
        for(j = 1; j < col; j++) {
            if(board[i][j] != 0) {
                board[i][j] = min(min(board[i-1][j], board[i][j-1]), board[i-1][j-1]) + 1;
                answer = max(answer, board[i][j]);
            }
        }
    }
    return answer * answer;
}