[백준 2923] 숫자 게임

[백준 2923 : 숫자 게임 ]

그리디..GREEDY..탐욕..욕심.. 너무 싫다.
한 8번? 틀렸는데
틀린 과정은

1) 처음엔 간단하게 생각했다. A,B의 MAX값 , MIN값을 계속 저장하면서
ANS = MAX(A_MAX+B_MIN,B_MAX+A_MIN) 이런식으로 출력했는데 틀렸다.
더 구체적으로 짜보자 자료구조 연습할겸
MAX_HEAP , MIN_HEAP을 짰고 했더니 역시나 틀렸다. 처음엔 런타임에러가 나서 왜그러지 하다가
벡터자료구조를 잘못짜서 그런것을 알고 로직 자체가 틀렸다는것을 깨달았다.
뭐가 틀렸지 하다가 질문 글을 보고 깨달았다.
3
1 1
2 2
2 2
가 있을땐 아무리 조합해도 4가 최대값에서 최솟값이 된다.

2) 어떤식으로 풀어볼까 하다가 배열에 숫자의 카운트를 해줬다. A[101]을 설정해 해당 숫자의 카운트를 늘려줬다.
벡터를 이용해서 새로운 숫자들만 PUSH해줬고 A는 1부터 B는 100부터 순서대로 카운트>0 일때만 더해줬는데
시간초과가 나왔다.
음! 시간만 줄이면 되겠다 싶었다.
여기까지의 코드는

비효율적이다. ACNT와 BCNT부분을 계산으로 가능하다고 이때 생각했다.

3) 정답이 나왔다.
BREAKPOINT라는 변수를 버리고 ACNT와 BCNT의 차를 이용해 ASI와 BSI를 이동했다.

그리디는 정말 어렵다. 특정 알고리즘도 아니고 그냥 구현해서도 안된다.
시간과 메모리 그리고 로직이 어떻게 돌아가야 할지를 전부 생각하면서 구현해야하기때문에 너무 까다롭다.
그리디 문제를 풀 때 처음에 틀렸습니다가 나오면 로직을 바꿔야 하기때문에 아직 나한텐 버거운듯.