3-E 뮤탈리스크 질문

Question

using namespace std ; vector< int > V; bool cmp ( int A , int B ){ return A > B; } int main (){ ios_base :: sync_with_stdio ( false ); cin . tie ( NULL ); cout . tie ( NULL ); int N, temp; cin >> N; for ( int i = 0 ; i < N; i++){ cin >> temp; V . push_back (temp); } int cnt = 0 ; while ( V . size ()){ sort ( V . begin (), V . end (), cmp); int dmg = 9 ; cnt++; for ( int i = 0 ; i < V . size (); i++){ V [i] -= dmg; dmg /= 3 ; } sort ( V . begin (), V . end (), cmp); for ( int i = V . size () - 1 ; i >= 0 ; i--){ if ( V [i] <= 0 ) V . pop_back (); else break ; } } cout << cnt; return 0 ; } 안녕하세요. 강사님. 항상 수업을 잘 가르쳐 주셔서 감사합니다. 우선, 해당하는 강의를 듣고 푸는 것은 이해를 했습니다. 하지만, 강의를 듣기 전, 뮤탈리스크가 SCV의 체력이 많은 순서대로 때리는 것이 맞겠다고 생각했고, 이를 토대로 풀어본 코드는 위와 같습니다. 위 코드에서 백터 V라는 전역변수를 사용해 입력을 받습니다. 이후, 해당 벡터를 내림차순(=큰 순서대로)으로 정렬하고, SCV HP를 9, 3, 1 순서로 깎았습니다. 이 후, 다시 내림차순으로 정렬하여 벡터의 마지막 인덱스부터 HP가 0 이하이면 pop_back()을 해주었습니다. 위와 같이, 풀었을 때, 주어진 테스트 케이스는 통과했지만, 문제 제출 시 틀렸다고 나온 상태 입니다. 혹시, 위 코드로 풀었을 때, 문제점을 여쭤보고 싶습니다.

mch473700 · Answer

와 저도 이 고민하고 있었는데.. 10/10/6 반례로 명쾌하게 해결했슴당 감사합니다.

큰돌 · Answer

먼저 그러한 생각은 잘하셨습니다. 큰순서대로 깍으면 된다는 논리는 생각해볼만하지만 이부분이 잘못되었습니다. 1. 무식하게 풀기를 먼저생각하고 이게 만약 안된다고 했을 때 2. 종우님이 하셨던 생각처럼 그리디적 방법을 생각해야 합니다. 또한 반례를 들자면 10 10 6 입니다. 종우님의 로직대로 계속해서 9 3 1로 하면 3번해야되지만 최적의 경우의수는 2번이죠? 감사합니다