[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; }
댓글
댓글 쓰기