[ 백준 ] 20127 / Y-수열

金弘均·2021년 9월 14일
0

Baekjoon Online Judge

목록 보기
21/228
post-thumbnail

# Appreciation

/*
 * Problem :: 20127 / Y-수열
 *
 * Kind :: Ad-Hoc
 *
 * Insight
 * - 수열의 맨 앞의 k개의 원소를 맨 뒤로 옮겨서
 *   증가수열 또는 감소수열을 만들어야 한다
 *   + 옮기는 횟수는 단 1번
 *     # 전체수열에서 부분적으로 증가하는 수열이 3개 이상이면
 *       이 방식으로 전체수열을 증가수열로 만드는 것은 불가능하다
 *       -> 전체수열에서 부분적으로 증가하는 수열이 2개면
 *          a_i > a_(i+1) 인 부분이 단 한곳 존재한다
 *          a_1 부터 a_i 까지 원소들을 맨 뒤로 옮겨서 증가수열로 만들기 위해서는
 *          a_1 >= a_N 이어야만 한다
 *          이때, k=i 이다
 *       -> 전체수열에서 부분적으로 증가하는 수열이 1개면
 *          전체수열이 이미 증가수열이므로 k=0 이다
 *     # 마찬가지로 전체수열에서 부분적으로 감소하는 수열이 3개 이상이면
 *       이 방식으로 전체수열을 감소수열로 만드는 것은 불가능하다
 *       -> 전체수열에서 부분적으로 감소하는 수열이 2개면
 *          a_i < a_(i+1) 인 부분이 단 한곳 존재한다
 *          a_1 부터 a_i 까지 원소들을 맨 뒤로 옮겨서 감소수열로 만들기 위해서는
 *          a_1 <= a_N 이어야만 한다
 *          이때, k=i 이다
 *       -> 전체수열에서 부분적으로 증가하는 수열이 1개면
 *          전체수열이 이미 감소수열이므로 k=0 이다
 *
 * Point
 * - 편의상 인덱스 넘버링(Index Numbering)은
 *   제로 베이스 넘버링(Zero-based Numbering)을 사용하였다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    int A[N];
    for (int i=0; i<N; i++)
        cin >> A[i];

    // Process
    /* up_cnt: i=1~(N-1) 에서 a_i < a_(i+1) 인 i 의 개수
     * up_k: i=1~(N-1) 에서 a_i < a_(i+1) 인 i 의 최댓값 */
    int up_cnt = 0, up_k = 0;
    /* down_cnt: i=1~(N-1) 에서 a_i > a_(i+1) 인 i 의 개수
     * down_k: i=1~(N-1) 에서 a_i > a_(i+1) 인 i 의 최댓값 */
    int down_cnt = 0, down_k = 0;
    for (int i=1; i<N; i++) {
        if (A[i-1] > A[i]) {
            down_cnt++;
            down_k = i;
        }
        if (A[i-1] < A[i]) {
            up_cnt++;
            up_k = i;
        }
    }

    /* 부분적으로 감소하는 수열의 개수 = up_cnt + 1
     * 부분적으로 증가하는 수열의 개수 = down_cnt + 1 */

    /* 감소수열을 만들 수 없는 경우 */
    if (up_cnt > 1 || (up_cnt == 1 && not(A[N-1] >= A[0]))) {
        up_k = -1;
    }

    /* 증가수열을 만들 수 없는 경우 */
    if (down_cnt > 1 || (down_cnt == 1 && not(A[N-1] <= A[0]))) {
        down_k = -1;
    }

    int ans;
    /* 감소수열 증가수열 모두 만들 수 있는 경우 */
    if (up_k != -1 && down_k != -1)
        ans = min(up_k, down_k);
    /* 증가수열만 만들 수 있는 경우 */
    else if (up_k != -1)
        ans = up_k;
    /* 감소수열만 만들 수 있는 경우 */
    else if (down_k != -1)
        ans = down_k;
    /* 만들 수 없는 경우 */
    else
        ans = -1;

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글