[BOJ] 6198번: Bad Hair Day

https://www.acmicpc.net/problem/6198

O(N**2) 풀이를 떠올릴 수 있지만 시간초과가 뜰 가능성이 농후합니다. 대신 현재까지 등장한 길이 중에서 strictly decreasing하는 sequence만 모아둔 stack(혹은 배열)을 생각해봅시다. 새로운 원소가 들어왔을 때 여전히 이 stack을 strictly decreasing하게 처리를 하고 나면 stack의 size가 곧 새로 들어온 원소의 hair를 볼 수 있는 소의 수입니다.

예를 들어 예제 입력인 10 3 7 4 12 2로 생각해보면

10이 들어왔을 때 -> 10 (+0)

3이 들어왔을 때  -> 10 3 (+1)

7이 들어왔을 때 -> 10 7 (+1)

4가 들어왔을 때 -> 10 7 4 (+2)

12가 들어왔을 떄 -> 12

2가 들어왔을 때 -> 12 2 (+1)

입니다.

각 원소는 반드시 한 번 stack에 등장하고, 한 번 혹은 0번 제거됨이 보장되므로 O(N)에 해결이 가능합니다.

https://github.com/blisstoner/BOJ/blob/master/6198.cpp