누적합1 [BOJ] 백준 1028번: 다이아몬드 광산 https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net R, C 가 750으로 (i, j) 좌표에서 우측 하단으로의 대각선 길이 DP[i][j][0], 좌측 하단으로의 대각선 길이 DP[i][j][1], 좌측 상단으로의 각선 길이 DP[i][j][2], 우측 상단으로의 대각선길이를 구해놓고 모든 좌표에 대하여 O(R*C*750*4)의 복잡도로 가능한 다이아몬드 크기를 구할 수 있습니다. (시간초과가 날것 같지만 가지치기를 통해 충분히 시간을 줄일 수 있습니다.) #include #include #i.. 2020. 8. 12. 이전 1 다음
