[백준] 2872 우리집엔 도서관이 있어

March 27, 2021 ( last updated : March 27, 2021 )
그리디 알고리즘 algorithm

https://github.com/sneakstarberry/

Abstract

[백준] 2872번 우리집엔 도서관이 있어

[백준] 2872번 우리집엔 도서관이 있어

백준 2872번

알고리즘 유형

풀이방법

예제는 너무 쉬우니 다른 예로 설명한다. 아래 예제를 보자.

7
1 3 5 4 2 6 7

위 예제를 보면 5, 6, 7를 제외한 모든 숫자가 정렬 되어야한다는 것을 알 수 있다.
이를 일반화 해보면 다음과 같다.

x는 예제의 idx이다. u는 연속되는 값 중 가장 작은 값이다.
x1, x2, u, x4, x5, … xn-2, u+1, n

이때 u이후 u+1까지의 모든 값들은 u보다 작을 수 밖에 없다. 그렇다면 u보다 작은 모든 수들은 정렬을 하기 위해서 위치를 옮겨야한다는 것이다.
그렇기 때문에 정답은 u-1이 나온다.

위 예제에서는 연속되는 가장 작은 수가 5이기 때문에 5-1 즉, 4가 정답이란 것을 파악할 수 있다.

이와 같은 논리로 코드를 짜면 된다.

#include <iostream>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, input, max_num, cnt;
  max_num = 1;
  cin >> n;
  cnt = n - 1;
  for (int i = 0; i < n; i++) {
    cin >> input;

    if (input > max_num) {
      if (max_num + 1 == input) {
        cnt--;
      } else if (max_num + 1 < input) {
        cnt = n - 1;
      }

      max_num = input;
    }
  }

  cout << cnt;
}

Originally published March 27, 2021
Latest update March 27, 2021

Related posts :

{# #}