[프로그래머스] 가장 큰 정사각형 찾기 (JS)

풀이 과정

DP
1. 2번째 다음 행과 열부터 시작해서 2중 반복
2. 현재 칸이 0이 아니면 위, 대각선 왼쪽 위, 왼쪽 값의 최솟값 + 1을 채워넣기
매번 최댓값 갱신
3. 모두 완료 후 최댓값의 제곱을 리턴

코드

function solution(board) {
  let result = 0;
  const [r, c] = [board.length, board[0].length];
  if (r < 2 || c < 2) return 1;

  for (let i = 1; i < r; ++i) {
    for (let j = 1; j < c; ++j) {
      if (board[i][j] === 0) continue;
      const cnt =
        Math.min(board[i - 1][j - 1], board[i][j - 1], board[i - 1][j]) + 1;
      board[i][j] = cnt;
      if (result < cnt) result = cnt;
    }
  }
  return result ** 2;
}

🤔

어떻게 해도 시간 초과가 나서 결국 다른 사람의 풀이 참고...
혼자 힘으로 풀기 어려운 문제가 점점 더 많아지는 것 같다.
이런 것도 DP라고 한다는 걸 새로 알게 되었고, 이런 방식을 생각해낸다는 것이 대단하게 느껴졌다.