1915

(C++) 백준 1915번 [가장 큰 정사각형]

백준 1915번 문제 [가장 큰 정사각형] 알고리즘 포스팅을 시작해보겠습니다. 다이나믹 프로그래밍 문제인데, 처음에 다른 방식으로 풀었다가 시간초과가 나서 그제서야 DP로 방향을 잡고 풀었으나, 추상화와 해결방법을 쉽게 찾지 못하다가 겨우 푼 문제입니다. 1. 문제 해결 방법 구상하기 - 입력값부터 받는 데 문제가 생깁니다. 그냥 cin 으로 해서 int값으로 입력받을 수는 없습니다. - 그렇다면 scanf를 이용하여 %1d 로 받을 수도 있고, 문자열 형태로 입력을 받은 후, -'0'을 해주어 int 값으로 다시 변환해줄 수도 있습니다. - 입력받은 후에 문제 해결은 어떻게 해야 할까요? - 다이내믹 프로그래밍이란 추상화, 즉 점화식이 굉장히 중요합니다. 위의 그림에서 가장 중앙에 있는 정사각형을 기준..