• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

질문있습니다.

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);

}

답변 1

답변을 작성해보세요.

0

안녕하세요^^

일단 같은 다이나믹 방법이면 효율성을 논할 정도의 차이는 없습니다.

case 2를 가지고 디버그를 해보면서 스스로 문제를 찾아보는게 우선인 것 같습니다.