본문 바로가기
Algorithm Solution/KOI Elementary School

[KOI 초등부] BOJ 17608 막대기 (2019 1차 대회)

by hygoni 2019. 12. 25.
불러오는 중입니다...

문제 유형 :  개인적으론 ad-hoc인듯

 

해설 : 

먼저 막대기의 길이를 배열에 저장, 막대기의 개수가 N이라고 했을때 오른쪽에서 바라보므로 N-1, N-2, ... , 0 이렇게 마지막 원소부터 차례대로 순회를 하는데, "지금까지 순회한 막대기 중 가장 긴 것"보다 길이가 긴 경우에만 개수를 더해주면 된다. 지금까지 순회한 막대기 중 가장 큰 것 보다 작거나 같은 경우는 눈에 보이지 않기 때문

 

문제의 테스트 케이스를 직접 그려보면 이해가 잘 된다.

 

구현 :

 

 

반응형

댓글0