프로그래머스 레벨2 문제 중 '땅따먹기'라는 문제입니다. DP 기본 문제입니다. 문제 출처 : 링크 DP 관련 문제 : 프로그래머스 '가장 큰 정사각형 찾기' 문제 풀이 포인트 완전 탐색으로 풀이를 시도하게 되면 시간 초과가 발생하는 문제였습니다. 그래서 각 단계별로 진행하는 과정에서 최대가 되는 값을 메모라이제이션 해야되는 문제였습니다. 1행의 경우는 이전 값이 없기에 그대로 메모라이제이션 됩니다. 2행 부터는 1행의 같은 열을 제외한 나머지 값들과 합을 구해보고, 그 합들 중 최대가 되는 값을 저장해야 됩니다. 가령 2행의 4열 값인 8을 보면 이전 행의 5와 합을 할 수 없기에 최대값은 11이 되는데, 메모라이제이션 배열을 보면 해당 값이 최대가 아닙니다. class Solution { privat..

프로그래머스 레벨2 문제 중 '숫자의 표현'이라는 문제입니다. DP 기본 문제입니다. 문제 출처 : 링크 DP 관련 문제 : 프로그래머스 땅따먹기 풀이 포인트 0과 1로만 배열이 되어있기 때문에 정사각형이 되는 지점에서 최대값을 메모라이제이션을 하면됩니다. 정사각형이 되는 지점을 찾는 것은 정사각형에서 오른쪽 아래를 기준으로 위, 왼쪽, 대각선이 모두 1이면 정사각형이라고 판단하면 됩니다. 위 내용을 기준으로 전체를 탐색합니다. 배열의 위치값이 1이면 해당 값을 기준으로 정사각형을 판단하고, 해당 위치의 메모라이제이션 값은 원래 board의 값으로 추출하는 것이 아니라, 메모라이제이션 배열에서 정사각형에 포함되는 값들 중 가장 작은 값 +1을 해주면 됩니다. 위 로직대로 동작하면 위 그림처럼 값이 채워지..