17608 막대기

이 문제를 처음 봤을 때에는 단순히 최댓값 구하는 문제인 줄 알고 후다닥 적었다가 당연히 틀렸다.

그럴 리가 없었는데... 아무튼 내가 생각한 풀이와 스택을 이용해서 푸는 거 두개를 적을려고 한다.

 

1. 내가 생각한 풀이

0~n-1까지 입력을 받으면서 가장 긴 막대기의 위치를 구한다.

가장 긴 막대기와 마지막 막대 사이에 있는 막대기(i번째 막대기라고 하자)를 하나하나 보면서 i번째 막대기가 가장 긴 막대기보다는 작고 마지막 막대보다는 크면 조건을 만족하는 막대기라고 생각했다. (count++해주었다)

여기서 고려했던 점은 가장 긴 막대기와 마지막 막대의 길이가 같을 때(가장 긴 막대가 마지막 막대가 되어도 상관없다)에는 count를 1만 더해주고, (사실 이 경우에는 조건을 만족하는 막대기가 그냥 1개이다)

가장 긴 막대기가 마지막 막대기보다 길 때는 count에 2를 더해주었다는 점이다. 

틀렸다고 나오는데 난 이유를 모르겠다,, 엉엉 시간초과인건지 아예 풀이에 문제가 있는 건지 모르겠다.

 

코드 : 

#include <iostream>
int a[100001];
using namespace std;

int main(){
int n, max=0;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
if(a[max]<a[i]) max=i;
}

int count;
if(a[max]==a[n-1]) count=1;
else if(a[max]>a[n-1]) count=2; 
for(int i=max;i<n-1;i++){
if(a[i]<a[max] && a[i]>a[n-1]) count++;
}

cout<<count;
}

 

2. 스택을 이용한 풀이

스택을 이용한 풀이는 감이 잘 잡히지 않아서 풀이를 참고하였다. : tunafish78.tistory.com/98 감사합니다,,

스택을 이용한 풀이는 막대기 하나를 넣으면서 넣는 막대기보다 작은(조건을 만족하지 않는 막대기)는 모두 pop하는 방식이다. 막대기 하나를 넣을 때 순서대로 pop만 하면 되는 이유는 이전 막대기를 넣을 때 그에 맞지 않는 막대기는 모두 pop당했기 때문이다. 약간 재귀의 느낌이 나만 난 것 같기는 하지만 어쨌든 그래서 i번째 막대기를 고려할때는 이미 이전 막대기까지 최적의 상태로 고려된 상태이므로 뭔가 더 고려하려고 노력하지 않아도 된다.

 

코드 : 

#include <iostream>

#include <stack>

using namespace std;

 

int a[1000001];

 

int main(){

int n;

cin>>n;

for(int i=0;i<n;i++) cin>>a[i];

 

stack<int> s;

for(int i=0;i<n;i++){

if(i==0) s.push(a[i]);

else{

while(!s.empty() && a[i]>=s.top(); i>=0){

s.pop();

}

s.push(a[i]);

}

}

cout<<s.size()<<endl;

}