[BOJ/Silver 5] 백준 28136 원, 탁!(C++)

문제 링크

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

28136번: 원, 탁!

 

문제

현빈이는 수열을 좋아한다. 그중에서도 오름차순으로 정렬된 수열이라면 단연코 환장한다.

선우는 수열과 수학을 사랑하는 현빈이를 골탕 먹이고자 현빈이에게 숫자가 적힌 접시가 원형으로 놓여있는 원탁을 내밀었다. 각 접시에는 시계방향으로 1부터 N까지 번호가 붙어있고, i번 접시에는 ai가 적혀있다. N번 접시 다음에는 1번 접시가 등장함에 유의하자.

현빈이는 수열을 시계방향으로 읽고 있고, 원탁의 특성상 접시에 적혀있는 숫자를 시계방향으로 읽다 보면 숫자가 순환되기 때문에, 현빈이는 정렬된 상태를 볼 수 없다. 이에 현빈이는 몇 번의 원, 탁!을 계획한다. 원, 탁! 한 번은 다음의 과정을 의미한다.

인접한 두 접시 사이의 연결을 끊는다.

위의 그림에서 1이 적혀있는 접시를 1번 접시라고 한다면, 3번과 4번 접시의 연결을 끊고, 5번과 1번 접시의 연결을 끊어 [1, 2, 4], [3, 5]의 정렬된 2개의 수열을 얻을 수 있다.

원, 탁!을 하는 데에 힘들었던 운동 부족 현빈이는 원, 탁!의 횟수를 최소화하여 정렬된 수열을 얻어내고 싶어 한다. 여기서 정렬된 수열이란, 시계방향으로 보았을 때 오름차순으로 정렬된 수열을 말한다. 원탁에 놓인 접시들의 정보가 주어질 때, 현빈이가 최소 몇 번의 원, 탁!을 하면 원하는 수열을 얻어낼 수 있는지 알아내는 프로그램을 만들어 주자.

입력

첫 번째 줄에는 접시의 개수 N(3 ≤ N ≤ 1,000,000)이 주어진다.

두 번째 줄에는 공백을 구분으로 ai가 주어진다. (1 ≤ i ≤ N; 1 ≤ ai ≤ 1,000,000)

출력

최소 몇 번의 원, 탁!이 필요한지 출력한다.

예제 입력 1

5
1 2 4 3 5

예제 출력 1

2

예제 입력 2

5
1 2 3 4 5

예제 출력 2

1

노트

오름차순 수열이란 뒤로 갈수록 숫자가 커지는 수열을 의미한다.

알고리즘 분류

• 그리디 알고리즘

풀이

A개의 정수를 0번째 접시부터 다음 접시와 비교하면서 현재 접시가 다음 접시보다 크거나 같다면 두 접시의 연결을 끊는다.

접시들은 원탁에 놓여 있으므로, 마지막 접시는 0번째 접시와 비교한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1000001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
int A[MAX];
int Answer;

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
}

void settings() {
    A[N] = A[0];
    for (int i = 0; i < N; i++) {
        if (A[i] >= A[i + 1]) {
            Answer++;
        }
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}