c언어 6198번 옥상 정원 꾸미기 (백준)

#include <stdio.h>
#define M 801

typedef struct Stack {
	int top;
	int arr[M];
}Stack;

int isEmpty(Stack *s) {return s->top == 0;}
void push(Stack *s, int e) {s->arr[s->top++] = e;}
int pop(Stack *s) { return s->arr[--s->top];}
int peek(Stack *s) {return s->arr[s->top-1];}
int cnt(Stack *s) {return s->top;}

int main(void) {
	int n;
	long long int ans = 0;
	Stack s;
	s.top = 0;
	scanf("%d", &n);
	
	while(n--) {
		static long long int tmp = 0;
		scanf("%lld", &tmp);
		if(isEmpty(&s)) push(&s, tmp);
		else {
			if(peek(&s) > tmp) push(&s, tmp);
			else {
				while(peek(&s) <= tmp && !isEmpty(&s)) {
					pop(&s);
				}
				push(&s, tmp);
			}
		}
		ans += cnt(&s)-1;
	} printf("%lld", ans);
	return 0;
}

 

 

풀이 : 스택을 이용합니다!

 

요소를 넣을 때마다 스택의 길이 - 1 을 누적한 것이

옥상 볼 수 있는 횟수입니다!

 

위의 코드는 c++로 적은 것을 c로 바꾼 것 입니다.

 

자세한 설명은 아래 링크에 있습니다.

 

https://h202.tistory.com/225

c++ 6198번 옥상 정원 꾸미기 (백준)