fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 17074 (C++) 정렬
최초 업로드: 2025-10-29 23:54:56
최근 수정 시간: 2025-10-29 23:54:56
게시자: rlatjwls3333
카테고리: 백준
조회수: 13
# [Silver I] 정렬 [문제 링크](https://www.acmicpc.net/problem/17074) ## 문제 설명 <p>정렬이란, 배열의 모든 원소가 비내림차순이 되도록 순서를 바꾸는 것을 말한다. 예를 들어 배열 [2, 1, 2, 3, 1]을 정렬하면 [1, 1, 2, 2, 3]이 된다.</p> <p>남규는 정수 <em>N</em>개로 이루어진 배열 하나를 갖고 있다. 이 배열에서, 남규는 맘에 들지 않는 수를 정확히 하나 골라서 버릴 것이다.</p> <p>예를 들어, 남규가 가진 배열이 [1, 2, 3, 2]라면, 남규는 1을 버려 [2, 3, 2]를 만들거나, 첫 2를 버려 [1, 3, 2]를 만들거나, 3을 버려 [1, 2, 2]를 만들거나, 두 번째 2를 버려 [1, 2, 3]을 만들 수 있다. 그리고 네 가지 경우 중 결과가 정렬된 것은 [1, 2, 2]와 [1, 2, 3] 두 가지이다. 남규는 이처럼, 수 하나를 버린 뒤 결과 배열이 정렬되어 있기를 원한다.</p> <p>남규가 갖고 있는 배열이 주어지면, 수 하나를 버려 정렬된 배열을 남기는 방법의 수를 구해보도록 하자.</p> ## 입력 <p>첫째 줄에 배열의 크기 <em>N</em>이 주어진다. (2 ≤ <em>N</em> ≤ 10<sup>5</sup>)</p> <p>둘째 줄에 배열의 원소<em> a<sub>i</sub></em>가 공백으로 구분되어 <em>N</em>개 주어진다. (-10<sup>9</sup> ≤ <em>a<sub>i</sub></em> ≤ 10<sup>9</sup>)</p> ## 출력 <p>남규가 수 하나를 버려 정렬된 배열을 만드는 경우의 수를 출력한다.</p> ## 풀이 0부터 i-1까지 비내림차순인지 확인하는 배열과, i+1부터 n-1까지 비내림차순인지 확인하는 배열을 사용하여 풀었습니다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 100'000; int a[MAX]; bool beforeSorted[MAX], afterSorted[MAX]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=0;i<n;i++) cin >> a[i]; for(int i=0;i<n;i++) { beforeSorted[i]=true; if(i && a[i-1]>a[i]) break; } for(int i=n-1;i>=0;i--) { afterSorted[i]=true; if(i<n-1 && a[i]>a[i+1]) break; } int cnt=0; for(int i=0;i<n;i++) { if(beforeSorted[i] && afterSorted[i] && (i==0 || i==n-1 || a[i-1]<=a[i+1])) cnt++; } cout << cnt; } ```