[백준(BOJ)] 1449번 : 수리공 항승 - C++[CPP]

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

1449번: 수리공 항승

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그리디 알고리즘
• 정렬

 

---

 

⊙ 문제 접근 과정

 

vector를 이용해 값을 입력받고 정렬을 해주었다.

그 후 temp 변수를 만들어 현재 위치와 다음 위치의 차이를 계속해서 빼주었다. (테이프가 소모되는 값)

만약 테이프가 남아있으면 계속 반복, 부족하면 count up 후 temp 초기화 후 반복.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N,L;
vector<int> v;

int main() {
    cin >> N >> L;

    for(int i=0;i<N;i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }

    sort(v.begin(),v.end());

    int result=1;
    int temp=L-1;

    for(int i=0;i<N-1;i++) {
        if(v[i+1]-v[i]<=temp) {
            temp-=v[i+1]-v[i];
        } else {
            temp=L-1;
            result++;
        }
    }
    cout << result;
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

그리디 알고리즘 위주로 문제를 풀고 있는데 생각보다 재미있다.

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!