이 문제를 스택으로 해결했었다. 그런데 음 스택으로도 다시 풀어보고, 분할 정복으로도 풀 수 있던데 두가지로 풀어보겠다. 이전에 스택했으니 일단 분할정복으로 하자.
보통 분할 정복은 절반씩 분할하는거 같다. 계속 분할해서 한개가 되고 두개로 합칠때 음?
어떻게 생각해야되는 걸까....
음 분할해서 해당 영역의 가장 큰 넓이를 찾으면 된다고 생각한다. 그리고 이제 두개를 합치면 되는거 같은데, 그렇다면 합칠때 양쪽 중에 더 작은 높이 * 양쪽 갯수 랑 두개 영역을 비교해서 가장 큰 넓이를 선택하게 한다.
이때 합병하면서 저장해야 되는 값은 가장 작은 높이, 합친 넓이이다. 가장 작은 높이랑 갯수를 알면 왼쪽 오른쪽을 합칠때 합쳐질 넓이를 알 수 있다.
재귀함수를 사용할텐데 매개 변수로 시작,끝 인덱스를 넘겨주면 갯수는 알 수 있다. 그럼 리턴으로
음 위의 방법으로는 답을 찾을 수 없다.
2 1 4 5 1 3 3의 경우 가운데 45가 합쳐지기가 어렵다.
5 1 3 3에서
5 1 중에 5 , 3 3은 같으니 합쳐서 6으로 하고 다시 이 두개를 합치면
6을 고르면
4 6 이랑 합치면 답인 9가 나올 수 가 없다. 즉 그냥 큰걸로 고르면 안된다.
근데 리턴은 가장 큰 영역을 하는게 맞다. 분할의 의미가 그러니까, 그러면 정복할때 그냥 무조건 큰것을 고르는게 아니라 경우를 따져봐야 할거 같다. 아 위에서 처럼 그 영역에서 가장 작은 걸로 양쪽을 합쳐보는게 아니라 양쪽에 맞닿아 있는 각각 한 기둥중 높이가 더 작은 것으로 합쳐봐야 한다. 왜냐하면 그 둘이 합쳐지지 않으면 어차피 다른놈들로도 합쳐지지 않는다.
음 위처럼 구현했는데 틀렸다.
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int N;
vector<int> vec;
int mergeNconquer(int st, int dt) {
if (dt - st == 0) {
return vec[st];
}
int Left, Right;
int bigger;
int merged=0;
int smaller;
int l1, r1;
int l2, r2;
int dis = dt - st;
l1 = st;
r1 = st + dis / 2;
l2 = st + dis / 2 + 1;
r2 = dt;
Left = mergeNconquer(l1,r1 );
Right = mergeNconquer(l2,r2);
bigger = max(Left, Right);
smaller = min(vec[r1], vec[l2]);
for (int i = l2; i <= r2; i++) {
if (vec[i] >= smaller)
merged += smaller;
else {
break;
}
}
for (int i = r1; i >= l1; i--) {
if (vec[i] >= smaller) {
merged += smaller;
}
else {
break;
}
}
bigger = max(bigger, merged);
return bigger;
}
int main() {
freopen("input.txt", "r",stdin);
cin >> N;
for (int i = 0; i < N; i++) {
int tmp;
cin >> tmp;
vec.push_back(tmp);
}
cout << mergeNconquer(0, N - 1);
}
원인으로 의심되는 이유는 바로 맞닿은 두 기둥보다 더 작은 넓이로 합쳐도 될거 같은데.....?
8
2
2
2
5
6
2
3
3
역시 이게 안된다. 이거 답은 16인데 10이 나온다. 그러면 맞닿은 애들 양쪽 모두의 블록을 기준으로 할 수는 없다. 시간초과 나올텐데 그냥 막하는거랑 똑같지 않나.
아 그래서 아래처럼 전부에 대해서 하니까 시간 초과가 뜬다.
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int N;
vector<int> vec;
int mergeNconquer(int st, int dt) {
if (dt - st == 0) {
return vec[st];
}
int Left, Right;
int bigger;
int merged=0;
int smaller;
int l1, r1;
int l2, r2;
int dis = dt - st;
l1 = st;
r1 = st + dis / 2;
l2 = st + dis / 2 + 1;
r2 = dt;
Left = mergeNconquer(l1,r1 );
Right = mergeNconquer(l2,r2);
bigger = max(Left, Right);
for (int k = st; k <= dt; k++) {
merged = 0;
smaller = vec[k];
for (int i = l2; i <= r2; i++) {
if (vec[i] >= smaller)
merged += smaller;
else {
break;
}
}
for (int i = r1; i >= l1; i--) {
if (vec[i] >= smaller) {
merged += smaller;
}
else {
break;
}
}
bigger = max(bigger, merged);
}
return bigger;
}
int main() {
freopen("input.txt", "r",stdin);
cin >> N;
for (int i = 0; i < N; i++) {
int tmp;
cin >> tmp;
vec.push_back(tmp);
}
cout << mergeNconquer(0, N - 1);
}
음 어떻게 해야 하지.....
두 영역을 합칠때 가장 큰 경우는 세가지로 분류 할 수 있을거 같다.
1. 만나는 가운데 기둥들 포함해서 가장 큰 경우
2. 만나는 기둥 빼고 오른쪽에서 가장 큰 경우
3. 만나는 기둥 빼고 왼쪽에서 가장 큰 경우.
4. 왼쪽 오른쪽에서 특정 길이로 가운데 포함에서 쭉 더할 경우. -> 특정 길이를 일일이 다해볼 수는 없다. 그래서 시간 초과가 나왔던 것.
아 궁금해서 찾아보니까
양쪽에 걸친 경우는, 영역을 높이가 양쪽 중 높이가 더 높은 부분으로 확장해가면서 넓이의 최대값을 저장해가면 된다.
이렇다는데, 저 말이 무슨 말인지는 알겠는데, 이해는 안되고 내 생각에는 높이 기준으로 해야되는데 왜 저렇게 하는지 모르겠다.
이건 전에 풀은 스택 풀이다.
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<string.h>
#include<string>
#include<stack>
#include<vector>
using namespace std;
vector<pair<int, int>> vec;
stack<pair<int,int>> st;
int N;
int arr[100001];
int dp[100001];
//가장 큰수는 -1로 정하기
//가장 오론쪽도 -1
//나머지는 왼쪽 기준 쭉가다가 자기보다 큰수만나면 큰수로 쭉 채우면되.
int main() {
cin >> N;
for(int i=0;i<N;i++){
scanf("%d", &arr[i]);
vec.push_back(make_pair(0,0));
}
st.push(make_pair(arr[0],0));
vec[0].first = 0;
for (int i = 1; i < N; i++) {
if (st.top().first > arr[i]) {
// vec[st.top().first].first = st.top().first; //left
while(st.top().first >= arr[i]) {
//vec[st.top().second].first = st.top().first; //left
vec[st.top().second].second = i; //right
st.pop();
if (st.empty() ) {
break;
}
vec[i].first = st.top().second+1;
}
st.push(make_pair(arr[i], i));
}
else if (st.top().first <= arr[i])
{
st.push(make_pair(arr[i],i));
vec[st.top().second].first = i;
}
}
while (!st.empty()) {
vec[st.top().second].second = N;
st.pop();
}
int max = 0;
int tmp;
for (int i = 0; i < N; i++) {
// printf("%d: %d %d\n",arr[i], vec[i].first, vec[i].second);
if (max < (tmp =((vec[i].second - vec[i].first)*arr[i])) ) {
max = tmp;
}
}
cout << max<<"\n";
}
6549 히스토그램에서 가장 큰 직사각형
28일 만에 다시 풀어본다.ㅋㅋ
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
long long int temp = (j - i + 1)*find(0, N - 1, 1, i, j);
if (temp > maxv) {
maxv = temp;
}
}
}코드의 이 부분에서 이중 반복문이라 안된거 같다.
https://kyunstudio.tistory.com/102 이분 코드 보고 풀었다.
양쪽을 병합할때 옆으로 확장하는 것을 잘못알아 듣고 했다. 근데 왜 이런식으로 하는지 모르겠네...으으
음 답을 알고나서 생각해 보니. 맞닫는 부분 양쪽으로 확장하면서 최대 넓이를 구해야 하는데 그것을 구하는 방법은 양쪽중에 가장 큰 사각형쪽으로 먼저 커지고 차차 다른 작은 사각형으로도 확장하면 결국 가장 높을때를 기준으로한 넓이와 가장 작을때를 기준으로 한 넓이를 둘다 구할 수 있게 된다.
나는 이것을 해결하려고 병합할때 각각의 모든 기둥에 대해 넓이를 구해보는 brute force 방법만을 생각했는데, 이렇게 양쪽으로 커다란 사각형으로 먼저 확장하는 방식을 사용하면 ( 대신 minHeight는 확장함에 따라 가장 작은 것을 골라야 한다.)
그리고 원래의 내 코드로는 까다로웠던 반례이다.
14
3 2 1 3 2 1 1 0 2 1 1 0 1 2
#define _CRT_SECURE_NO_WARNINGS
#define NUMBER 100000
#define MAXV 1000000000001
#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<long long int> arr;
long long int min_long(long long int a, long long int b)
{
if (a < b) {
return a;
}
else {
return b;
}
}
long long int max_long(long long int a, long long int b)
{
if (a < b) {
return b;
}
else {
return a;
}
}
long long int find(int start, int end) {
int mid = (start + end) / 2;
if (start == end) {
return arr[start];
}
long long int leftBlock = find(start, mid);
long long int rightBlock = find(mid + 1, end);
long long int middleBlock=0;
long long int minHeight;
int index;
if (arr[mid] < arr[mid + 1])
{
index = mid;
minHeight = arr[mid];
}
else {
index = mid+1;
minHeight = arr[mid + 1];
}
int cnt=1;
int low, high;
low = mid;
high = mid;
while (start <= low && high <= end) {
if (low-1 >= start &&(high == end || arr[low - 1] > arr[high + 1])) {
low--;
minHeight = min_long(minHeight, arr[low]);
cnt++;
}
else if(high+1 <= end){
high++;
minHeight = min_long(minHeight, arr[high]);
cnt++;
}
else {
break;
}
middleBlock = max_long(cnt*minHeight, middleBlock);
}
/*
for (int i = index; i <= end&& arr[i] >= minHeight; i++) {
cnt++;
minHeight = min_long(arr[i], minHeight);
}
for (int i = index - 1; i >= start&& arr[i] >= minHeight; i--) {
cnt++;
minHeight = min_long(arr[i], minHeight);
}
middleBlock = cnt * minHeight;
*/
long long int answer = max_long(leftBlock, middleBlock);
answer = max_long(answer, rightBlock);
return answer;
}
int main() {
freopen("input.txt" , "r",stdin);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
while (N) {
long long int maxv = 0;
for (int i = 0; i < N; i++)
{
long long int tmp;
cin >> tmp;
arr.push_back(tmp);
}
//init(0, N - 1, 1);
cout << find(0, N - 1) << "\n";
cin >> N;
arr.clear();
}
return 0;
}
'알고리즘 문제 풀기' 카테고리의 다른 글
| 프로그래머스 - 힙 : 더 맵게,라면 공장, 디스크 컨트롤러 (0) | 2020.01.05 |
|---|---|
| 프로그래머스 - 카카오 2018 블라인드 테스트 (추석 트래픽) (0) | 2020.01.04 |
| 프로그래머스 - 카카오 2020 블라인드 테스트 (블록 이동하기, 문자열 압축) (0) | 2020.01.02 |
| 프로그래머스 - 스택/큐 : 프린터, 쇠막대기, 주식 가격 (0) | 2019.12.30 |
| 프로그래머스 - 스택 : 탑, 다리를 지나는 트럭, 기능개발 (0) | 2019.12.27 |