[DP] 2차원 배열의 모든 부분 합 구하기 + pro 문제_부동산
일단 pro문제부터 보자.
김여사는 땅을 매입하려고 한다. 현재는 모든 땅들이 동일한 가격이지만
부동산 전문가 김군의 말에 따르면 5년뒤에는 땅 별로 값의 변화가 있을 것이라고 한다.
김여사는 땅을 직사각형 형태의 구역으로만 매입이 가능하고 두개 이상의 구역은 매입이 불가능하다.
R x C 로 된 땅이 제시된다. L 은 현재의 가격이고 각 땅에는 5년 뒤 가격이 적혀있다.
L 이 5인 경우는 땅 전체를 매입하는 것이 가장 좋고 시세차익은 91이다.
L 이 10인 경우는 노란색의 구역만 매입하는 것이 가장 좋고 시세차익은 12이다.
L 이 20인 경우는 시세차익을 얻을 수 없기때문에 땅을 매입하지 않는 것이 좋다.
김여사가 5년 후에 가장 큰 시세 차익을 얻을 수 있도록 프로그램을 개발하여라.
시세 차익이 가장 큰 경우와 그때의 땅 매입가를 구하시오
시세 차익이 가장 큰 경우가 여러 개 경우라면 땅 매입가가 가장 적은 경우를 선택한다.
예시)
현재의 땅 가격이 3이고 5년 뒤 땅 가격이 아래와 같을 경우
1 5 2 4 3 에서 시세 차익이 가장 큰 경우는 아래와 같다
5
5 2 4
5 2 4 3
그 중에서 땅 매입가가 가장 적은 경우는 첫번째이기때문에 정답은
#1 2 3 이 된다.
[조건]
1. 1< = R / C <=300
2. L(현재 땅 매입가)는 500,000,000 이하
3. 5년 뒤 땅 가격은 1000,000,007 이하
[Sample Case]
5
1 5 3
1 5 2 4 3
4 4 5
12 9 9 11
8 12 11 9
8 15 13 9
13 9 12 11
4 4 10
12 9 9 11
8 12 11 9
8 15 13 9
13 9 12 11
4 4 20
12 9 9 11
8 12 11 9
8 15 13 9
13 9 12 11
5 1 50
35
25
300
40
50
출력
#1 2 3
#2 91 80
#3 12 60
#4 0 0
#5 250 50
으음 언뜻보면 어렵지 않은 문제인것 같다.
meansoup.blogspot.com/2017/09/blog-post.html
2차원 배열의 부분합 구하기 - make better code
배열은 프로그래밍에서 가장 많이 쓰이는 자료구조 중 하나입니다. 그만큼 배열을 잘 다루는 것이 프로그래밍을 잘 하는 것이자, 개발이나 여러 문제 해결에 도움이 되는 측면이 크죠. 오늘은
meansoup.blogspot.com
이것을 인용해서 4중 포문으로 해버리면 쉬울꺼 같
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
import java.util.*;
import java.io.*;
import java.math.*;
public class D210415_pro190309_부동산 {
public static void main(String[] args) throws IOException {
//System.setIn(new FileInputStream("input2.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(br.readLine());
for(int z = 1 ; z <= tc ; z++) {
int x,y;
long L;
StringTokenizer st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
L = Long.parseLong(st.nextToken());
long[][] arr_cha = new long[x+1][y+1];
long[][] arr_cha_sum = new long[x+1][y+1]; // arr_cha의 누적합
for(int i = 1 ; i <= x ; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1 ; j <= y ; j++) {
arr_cha[i][j] = Integer.parseInt(st.nextToken()) - L;
}
}
for(int i = 1 ; i <= x ; i++) {
for(int j = 1 ; j <= y ; j++) {
//arr_cha_sum[i][j] == arr_cha[1][1] ~ arr_cha[i][j]의 합이다.
arr_cha_sum[i][j] = arr_cha_sum[i-1][j] + arr_cha_sum[i][j-1] -arr_cha_sum[i-1][j-1] + arr_cha[i][j];
System.out.print(arr_cha[i][j] + " ");
}
System.out.println();
}
long ans1 = 0; // 가장 큰 시세차익
long ans2 = Long.MAX_VALUE;; // 땅 매입가
long cnt = 0;
for(int i = 1 ; i <= x ; i++) {
for(int j = 1 ; j<= y ; j++) {
// i, j부터 시작
long benefit = 0;
long buy_price = Long.MAX_VALUE;
for(int k = i ; k <= x ; k++) {
for(int l = j ; l <= y ; l++) {
cnt++;
System.out.println(i + " " + j + " " + k + " " + l);
long tmp_benefit = arr_cha_sum[k][l] - arr_cha_sum[k][j-1] - arr_cha_sum[i-1][l] + arr_cha_sum[i-1][j-1];
long tmp_buyprice = (k-i+1)*(l-j+1)*L;
if(ans1 < tmp_benefit) {
ans1 = tmp_benefit;
ans2 = tmp_buyprice;
}
else if(ans1 == tmp_benefit && ans2 > tmp_buyprice) {
ans1 = tmp_benefit;
ans2 = tmp_buyprice;
}
}
}
}
}
if(ans1 == 0)
System.out.println("#"+z+" 0 0");
else
System.out.println("#"+z+" "+ans1+" "+ans2);
//System.out.println("#"+z+" "+ans1+" "+ans2 +" "+ cnt);
}
}
}
|
cs |
지만 이렇게 하면 TIMEOUT이 걸린다. 프로문제가 괜히 프로문제겠나????
실제로 n을 300으로 넣고 72번째줄의 cnt를 추출해보면
2억정도의 값을 나오면서 터질 것이다.
이 브루트 포스 경우의 수를 어떻게 하면 줄일 수 있을까????
일단 뺄 수 있는 방법을 생각해보자.
여기서 이것을 찾아야 한다.
정답이 아니라는 것이다!!!!!!!
그리고 문제에서 시세 차익이 가장 큰 경우가 여러 개 경우라면 땅 매입가가 가장 적은 경우를 선택한다.
라는것 때문에 특정구간이 0이여도 마이너스와 똑같은 조건을 받는다!!!!!
이것을 응용해서 해야 하는데
정말 조심해야 할 것이 있다.
으음 그러면 기준을 잡을 arr_cha[i][j] 의 값이 마이너스이면 이 기준값은 skip 하면 되지 않나??
밑에 행렬을 보자.
만약 노란색으로 칠한 arr_cha[i][j] 기준값이 마이너스라고 스킵을 해버리면
윗 그림의 오른쪽이 정답인데 어떻게 생각해야 할지 무한의 굴레에 빠지게 된다.
결론적으로 우리가 skip해야 하는 것은 기준점(1개의 값)이 아니라 기준구간(1개이상의 구간합)을
잡아야 한다는 것이다. 그러면 구간을 어떻게 잡으면 좋을까.....
그래서 구했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
import java.util.*;
import java.io.*;
import java.math.*;
public class D210418_pro190309_부동산_more {
public static void main(String[] args) throws IOException {
//System.setIn(new FileInputStream("input2.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(br.readLine());
for(int z = 1 ; z <= tc ; z++) {
int x,y;
long L;
StringTokenizer st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
L = Long.parseLong(st.nextToken());
long[][] arr = new long[x+1][y+1];
long[][] arr_rowsum = new long[x+1][y+1]; // 각 행별로 누적합을 구한다. 1행의 sum값, 2행의 sum값.......
for(int i = 1 ; i <= x ; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1 ; j <= y ; j++) {
arr[i][j] = Integer.parseInt(st.nextToken()) - L;
arr_rowsum[i][j] = arr_rowsum[i][j-1] + arr[i][j];
}
}
/*
for(int i = 1 ; i <= x ; i++) {
for(int j = 1 ; j <= y ; j++)
System.out.print(arr_rowsum[i][j] + " ");
System.out.println();
}
*/
long ans = 0; // 최대 이윤
long ans2 = Long.MAX_VALUE; // 부동산 투자 금액
for(int i = 1 ; i <= y ; i++) {
for(int j = i ; j <= y ; j++) {
long tmp_sum = 0;
int h = 1; // 구간을 품을 시작값
for(int k = 1 ; k <= x ; k++) {
tmp_sum += (arr_rowsum[k][j] - arr_rowsum[k][i-1]);
if(tmp_sum > ans) {
ans = tmp_sum;
ans2 = (j-i+1)*(k-h+1)*L; // 구간의 넓이
}
else if(tmp_sum == ans) {
ans2 = Math.min(ans2, (j-i+1)*(k-h+1)*L);
}
else if(tmp_sum <= 0) {
tmp_sum = 0;
h = k+1;
}
}
}
}
if(ans == 0) // 아무것도 없으면 ans2가 MAX값이 나와서 보정해줌
System.out.println("#"+z+" 0 0");
else
System.out.println("#"+z+" " + ans+ " " + ans2);
}
}
}
|
cs |
정답도 잘 나오고 n이 300일 때에도
1354만번 탐색으로 시간내로 도달한다.