Post List

[BOJ] 백준 2847 게임을 만든 동준이

[BOJ] 백준 2847 게임을 만든 동준이



이 문제는 양수의 입력이 주어졌을때 입력된 양수 집합이 오름차순이 되게끔 만들면 되는 문제 입니다. 따라서 인접한 배열끼리의 대/소 판별을 해야 하는데, 이를 맨 앞에 인덱스 부터 진행하게 된다면, 앞에서는 오름차순이었는데, 뒤로 갈수록 앞의 오름차순을 수정해야 하는 일이 일어날 수 있습니다.(6 5 4 8 -> 4 5 4 8 -> 4 3 4 8 -> 4 3 4 8 ...?)
이 경우 문제가 매우 복잡해지고, 문제에서 점수 내리기를 최소화 하는 방법을 찾아야 한다고 하였으므로, 배열을 앞에서부터 접근하면 안됩니다.
배열의 맨 뒤 인덱스부터 접근한다면, 위에 언급한 문제가 해결됩니다. 모호했던 대/소 관계 구분을 확실하게 짚고 넘어가기 때문 입니다.




소스코드 :


#include 
#include 
using namespace std;

int main() {
 int t;
 cin >> t;
 vector v;
 for (int i = 0; i < t; i++) {
  int num;
  cin >> num;
  v.push_back(num);
 }
 int cnt = 0;
 for (int i = t - 1; i >= 1; i--) {
                // 배열의 뒷쪽 인덱스부터 접근.
  while (v[i] <= v[i - 1] ) {
   if (v[i - 1] - 1 > 0) {
    v[i - 1]--;
    cnt++;
   }
   else break;
  }
 }
 cout << cnt << endl;
}

댓글