반응형
📖 문제
💡 풀이 방식
• DP
. 입력받은 2차원 배열의 행이나 열의 크기가 1이라면 바로 1을 출력하고 종료하게 한다. (예외처리, TC 1)
. 그게 아니라면, 2차원 배열을 (왼쪽 위 vs 왼쪽 vs 위쪽) 세 칸中 가장 작은 값 + 1을 해 갱신한다.
. 새롭게 완성된 2차원 배열에서 최댓값을 찾아 출력한다.
- dp 배열의 의미 : 현재 칸 (i, j)까지의 가장 긴 정사각형 길이 (여기서는 그냥 입력받은 2차원 배열 그대로 활용)
- dp 점화식 : (왼쪽, 위, 왼쪽 위) 세 칸 中 최솟값 + 1
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
import java.util.*;
class Solution {
public int solution(int[][] board) {
int answer = 0;
int r = board.length;
int c = board[0].length;
// board의 행 또는 열이 1인 경우 예외처리
if(r < 2 || c < 2) {
return 1;
}
for(int i = 1 ; i < r ; i++) {
for(int j = 1 ; j < c ; j++) {
if(board[i][j] == 0) continue;
// (왼쪽 위 vs 왼쪽 vs 위쪽) 세 칸 중 가장 작은 값 + 1을 해 채운다.
board[i][j] = Math.min(board[i-1][j-1], Math.min(board[i-1][j], board[i][j - 1])) + 1;
answer = Math.max(answer, board[i][j]);
}
}
return answer*answer;
}
}
|
cs |
💦 어려웠던 점
- 브루트포스로 풀려다가 장렬하게 전사했다.. 이런 문제는 dp문제라는 걸 바로 간파했어야 했는디,,
- 2차원 누적합 문제 점화식으로 풀어봤는데,, 이 문제는 칸의 숫자값을 모두 더하는 누적합 문제가 아니라 그냥 (왼쪽, 위, 왼쪽 위) 세 칸 中 제일 작은 값 + 1해서 정사각형 길이를 구하면 되는 문제였던 더 쉬운 편이었던 것이다,,
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
(참고)
반응형
'코테 > 프로그래머스' 카테고리의 다른 글
[프로그래머스/Level2] 하노이의 탑 (JAVA) (0) | 2024.01.24 |
---|---|
[프로그래머스/Lv. 2] 미로 탈출 (JAVA) (0) | 2024.01.24 |
[프로그래머스/Lv. 3] 이중우선순위큐 (JAVA) (0) | 2024.01.17 |
[프로그래머스/Lv. 3] 최고의 집합(JAVA) (0) | 2024.01.17 |
[프로그래머스/Lv. 2] 땅따먹기 (JAVA) (0) | 2024.01.16 |