-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
90점이 나옵니다!!! (51번)
22.08.17 23:18 작성 조회수 202
0
선생님의 DP 방법을 듣고서
제 스스로 코드를 짜봤는데
이게 자꾸 Input 2에서 오류가 나는데 이유를 모르곘습니다....!
테스트시 input 2를 넣었을때)
나와야 하는 값 => 1231
제 값 => 1208
저 같은 경우에는
- 선생님처럼 반복문 하나에다 오렌지 값들의 합을 넣지 않았고,
- 따로 dy 배열을 만들지 않고 그냥 맨 처음에 input으로 받은 배열에다가 채웠습니다!
- 맨위 가로와 맨왼쪽 세로만 세우고 나서
- 그 다음에 나머지 부분에 오렌지 값의 합을 넣도록했습니다!
문제에 나온 예시로는 오렌지 값이 정답과 같이 들어갑니다
input2만 다르게 나와요! ㅜㅜ 이유를 모르겠습니다!! 도와주세요 .....
#include <iostream>
using namespace std;
int main() {
int H,W;
int max = -2147000000;
int arr[701][701];
int myH, myW;
// input
scanf("%d %d", &H, &W);
for(int i=0; i<H; i++){
for(int j=0; j<W; j++) scanf ("%d", &arr[i][j]);
}
scanf("%d %d", &myH, &myW);
// orange
// 각 '칸까지의 사각형'의 합으로 채우기
// [1] 테두리 채우기
for(int i=1; i<H; i++){ // 왼 세로
arr[i][0] = arr[i-1][0] + arr[i][0];
}
for(int j=1; j<W; j++){ // 위 가로
arr[0][j] = arr[0][j-1] + arr[0][j];
}
// [2] 나머지 칸 채우기
for(int i=1; i < H; i++){
for(int j=1; j < W; j++){
arr[i][j] += arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
}
}
for(int i=0; i < H; i++){
for(int j=0; j < W; j++){
printf("%d ", arr[i][j]);
}
printf("\n");
}
// [3] 최대의 오렌지 갯수 구하기
for(int i=myH; i<H; i++){
int cnt = 0;
for(int j=myW; j<W; j++){
cnt = arr[i][j] - arr[i][j-myW] - arr[i-myH][j] + arr[i-myH][j-myW];
if(max < cnt) max = cnt;
}
}
// output
printf("%d", max);
return 0;
}
it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
51. 영지 (territory) 선택 (large : 2차원 배열 구간합 : 제한시간 1초 : DP)
강의실 바로가기
답변을 작성해보세요.
1
김태원
지식공유자2022.08.24
안녕하세요^^
코드를 보니 별 이상 없어보이는데...
arr[0][0]부터 오렌지를 넣은 것 같은데,
for(int i=myH; i<H; i++){
int cnt = 0;
for(int j=myW; j<W; j++){
cnt = arr[i][j] - arr[i][j-myW] - arr[i-myH][j] + arr[i-myH][j-myW];
if(max < cnt) max = cnt;
}
}
for에서 i와 j가 myH와 myW부터 시작하는게 맞는지 여기가 의심스럽습니다.
답변 1