-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
질문있습니다.
21.04.01 22:17 작성 조회수 154
0
선생님, 안녕하세요
선생님께서는 dp배열갱신하실 때
주어진 높이와 너비에서부터 시작을 하셨는데
저와 같은 경우는 i=1 j=1 즉
1,1시작점에서부터 시작을 하되
i+h가 H를 넘어서지 않고 j+w가 W를 넘어서지 않는 조건,
그리고 i-1>=1 j-1>W인 조건 이 두 조건을 충족하는 범위 내에서만
dp를 갱신하도록 해줬는데요
이게 선생님 방식보다 어떤 면에서 비효율인지 궁금합니다.
심지어 case 2는 틀렸다고 나오네요ㅜㅜㅜㅜ문제가 뭘까요?
#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
int H, W;
int map[701][701];
int dp[701][701];
int dp2[701][701];
bool visited[701][701];
int h, w;
int main() {
cin >> H >> W;
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
cin >> map[i][j];
}
}
cin >> h >> w;
dp[1][1] = map[1][1];
for (int i = 2; i <= H; i++) {
dp[i][1] = dp[i - 1][1] + map[i][1];
}
for (int i = 2; i <= W; i++) {
dp[1][i] = dp[1][i - 1] + map[1][i];
}
/*printf("\n");
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
printf("%d ", dp[i][j]);
}
printf("\n");
}*/
for (int i = 2; i <= H; i++) {
for (int j = 2; j <= W; j++) {
dp[i][j] = map[i][j] + (dp[i][j - 1] + dp[i - 1][j]) - dp[i - 1][j - 1];
}
}
//printf("\n");
//for (int i = 1; i <= H; i++) {
// for (int j = 1; j <= W; j++) {
// printf("%d ", dp[i][j]);
// }
// printf("\n");
//}
//printf("\n");
////이 부분이 질문입니다!!!!!///////
int ans = -1;
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
if (i + h <= H && i + w <= W && i - 1 >= 1 && j - 1 >= 1) {
dp2[i][j] = dp[i + h - 1][j + w - 1] + dp[i - 1][j - 1] - dp[i - 1][j + w - 1] - dp[i + h - 1][j - 1];
if (ans < dp2[i][j]) { ans = dp2[i][j]; }
}
else {
continue;
}
}
}
printf("%d", ans);
}
it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
51. 영지 (territory) 선택 (large : 2차원 배열 구간합 : 제한시간 1초 : DP)
강의실 바로가기
답변을 작성해보세요.
0
김태원
지식공유자2021.04.01
안녕하세요^^
일단 같은 다이나믹 방법이면 효율성을 논할 정도의 차이는 없습니다.
case 2를 가지고 디버그를 해보면서 스스로 문제를 찾아보는게 우선인 것 같습니다.
답변 1