[2022 KAKAO BLIND RECRUITMENT] 파괴되지 않은 건물

[uijin-j]

🔗 파괴되지 않은 건물

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java // 19:49 START! class Solution { // 무식한 방법 O(nmk) -> 1000 * 1000 * 250,000 시간초과 // 어렵다.. 누적합 public int solution(int[][] board, int[][] skill) { int n = board.length; int m = board[0].length; int[][] affected = new int[n+1][m+1]; for(int[] s : skill) { int toSum = ((s[0] == 1) ? -1 : 1) * s[5]; int x1 = s[1]; int y1 = s[2]; int x2 = s[3]; int y2 = s[4]; affected[x1][y1] += toSum; affected[x1][y2+1] += (toSum * -1); affected[x2+1][y1] += (toSum * -1); affected[x2+1][y2+1] += toSum; } for(int i = 0; i < n; ++i) { for(int j = 1; j < m; ++j) { affected[i][j] += affected[i][j-1]; } } for(int i = 1; i < n; ++i) { for(int j = 0; j < m; ++j) { affected[i][j] += affected[i-1][j]; } } int count = 0; for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { if(board[i][j] + affected[i][j] > 0) count++; } } return count; } } ```

코멘트

- 문제 유형 파악하는게 정말정말 어려운 문제인 것 같습니다.. 완탐은 시초나는데, 누적합, DP, 투포인터 다 생각해봐도 도저히 감을 못잡겠더라구요ㅜㅜ 그래서 풀이를 봤습니다..
- 누적합 문제인데, 일반적인 누적합은 첫지점부터 모든 지점까지 누적합을 구한 뒤, sum[j] - sum[i] 식으로 i ~ j 구간 합을 이용을 하는데, 이 문제는 구간합이 아니라 각 칸의 누적합을 구하는.. 아주 까다로운 문제였숩니다.. 아이디어를 얻으려면 수학적 사고력이 필요한 것 같아요🥲

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

```cpp #include #include using namespace std; //0605~0621 정확도만 맞음확도만 맞음 //시간초과 날 것 같은데 그리디 말고 방법이 생각 안남 //누적합 int type; int r1,c1,r2,c2,degree; int sum[1001][1001]; int solution(vector> board, vector> skill) { int answer = 0; for(int i=0;i0) answer++; } } return answer; } ```

코멘트