inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

51. 영지 (territory) 선택 (large : 2차원 배열 구간합 : 제한시간 1초 : DP)

질문있습니다.

209

celestial_

작성한 질문수 72

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

}

C++ 코테 준비 같이 해요!

답변 1

0

김태원

안녕하세요^^

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

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

테스트 케이스 질문

0

367

1

병합정렬 시간복잡도 질문

0

458

1

41.연속된 자연수의 합 문제풀이에서 수학적인 원리를 모르고 있습니다.

0

1339

2

질문드립니다.

0

371

1

질문드립니다!

0

425

1

dev 프로그램 질문

0

270

1

문제가 이해가 안되요

0

371

1

4번 나이차이 문제 접근법 질문 드립니다.

0

301

1

source file not compiled

0

1029

3

59번 질문드립니다.

0

366

1

25번 문제 질문

0

343

1

4. 나이차이 문제 질문입니다.

0

364

1

90번 라이언 킹 심바 1번 테스트 케이스

0

464

1

71번 문제 전역 변수 질문 있습니다

0

353

1

75번, 79번 priority_queue관련

1

351

1

75.최대 수입 스케줄

0

390

2

복면산 정답의 수

0

424

1

테스트 케이스에 대해서

0

438

1

수업 내용 질문입니다!

1

226

1

풀어보면 좋은 문제 목록 - 2580 스토쿠 DFS 질문입니다!!

0

812

2

12. 플로이드-와샬(그래프 최단거리) . 27:25초

0

248

1

다른 풀이 방식

0

310

1

크루스칼 vs 프림

0

300

1

숫자 총개수 small 질문있습니다.

0

231

1