SWEA - 증가하는 사탕 수열 (C++)

 

처음엔 이분탐색을 통해 풀이하려 했는데 쉬운 그리디 or 구현 문제이다.

 

경우를 나누어 볼 수 있다.

 

1. 처음부터 사탕 주머니가 오름차

2. 둘 중 하나라도 3번째 주머니보다 많이 차있음

 

만약 4 7 4 순서로 되어있다면 -> 2 3 4 순서로 만들어야한다. 즉, 최댓값이 정해져있다. 

첫번째 값은 candy[2] - 2

두번째 값은 candy[2] - 1

 

그러므로 만약 지금 사탕의 값이 위 임계값보다 크다면 임계값으로 바꿔주고 먹은 사탕을 샌다.

단 1 1 7 의 경우처럼 임계값에 걸리지 않지만 오름차가 아닌 경우가 있으므로 오름차가 맞는지 확인하는 로직까지 추가해주면 쉽게 답을 맞출 수 있다.

 

#include <iostream>

using namespace std;

int main(){
    int T; cin >> T;

    for(int t = 0; t < T; t++){
        bool flag = true;

        int arr[3];

        for(int i = 0; i < 3; i++) cin >> arr[i]; // 2 1 7
        
        if(arr[2] < 3) flag = false;
        
        int firstValue = arr[2] - 2;
        int secondValue = arr[2] - 1;        // 1 1 3
        int answer = 0;
        if(firstValue < arr[0]){
            answer += (arr[0] - firstValue);
            arr[0] = firstValue; // 7 4 3
        }

        if(secondValue < arr[1]){
            answer += (arr[1] - secondValue);
            arr[1] = secondValue;
        }

        for(int i = 0; i < 2; i++){
            if(arr[i] >= arr[i + 1]) flag = false;
        }

        if(flag) cout << '#' << t + 1 << ' ' << answer << '\n';
        else cout << '#' << t + 1 << ' ' << -1 << '\n';
    }
}