Algorithm/Algorithms Practice
[BOJ/C++] 스네이크버드(16435번)
Patrick_
2022. 5. 12. 14:49
1. 문제 개요
https://www.acmicpc.net/problem/16435
16435번: 스네이크버드
첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다.
www.acmicpc.net
1-1. 설명
스네이크버드는 뱀과 새의 모습을 닮은 생물체이다. 주요 먹이는 과일이며 과일 하나를 먹으면 길이가 1만큼 늘어난다. 과일들은 지상으로부터 일정 높이를 두고 떨어져 있으며, i번째 과일 높이는 h_i이다. 스네이크버드는 자신의 길이보다 작거나 같은 높이에 있는 과일을 먹을 수 있다. 스네이크버드의 처음 길이가 L일 때 과일들을 먹어 늘릴 수 있는 최대 길이를 구하시오.
1-2. 제한 사항
- i는 1이상 N이하의 자연수
- 과일의 개수인 N은 1이상 1,000이하의 자연수
- 스네이크버드 초기 길이 정수인 L은 1이상 10,000 이하
- 첫번째 줄에는 N과 L이 주어지고 두번째 줄에는 각 과일들의 높이가 주어짐
2. 구현
2-1. 풀이
입력받고 단순하게 둘째 줄에 존재하는 각 과일들의 높이를 저장하여 오름차순으로 정렬해준다. 그리고 반복문을 돌려 하나씩 검사해보고 스네이크버드의 길이가 과일의 높이보다 높으면 스네이크버드가 과일을 섭취해 1씩 커지고 낮으면 반복문이 종료되게끔 한다.
2-2. 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int fruitCount, snakeLength, height;
cin >> fruitCount >> snakeLength;
vector<int> FruitHeights;
for (int i = 0; i < fruitCount; i++) {
cin >> height;
FruitHeights.push_back(height);
}
sort(FruitHeights.begin(), FruitHeights.end());
for (int fruitHeight : FruitHeights) {
if (fruitHeight <= snakeLength) snakeLength++;
else break;
}
cout << snakeLength;
}