분류

: 그리디..??

문제풀이 전략

• 완탐인가?
  : 완탐으로 하기에는 원소 하나를 보고 3가지 경우의 수이다.
  그런데 n이 100만이라고 한다.

그러면 3의 100만승의 경우의 수가 되는데, 따라서 완탐은 불가하다.
-> 다른 방법이 있을까???? 생각.

문제 풀이 전략

: 계속 생각을 하다가
이런생각을 했따.

• 3 5 9 를 보면 최대 이익이 6 + 4 -> 10이다.
  그런데 3의 입장에서는 5에서도 팔아도 이익인데,
  더 큰 이익을 위해서 9에서 팔았네????
  -> 음.... 맨 뒤 값이 엄청 크면 사이에 큰값이 있어도 별 필요 없다는 생각을 함.
  --> 그래서 뒤에서부터 시작해보면 어떨까?? 생각을 했다.
  기준이 되는 값을 먼저 정하고 타겟값으로 sum 누적할지? 아니면 target 값 변경할지 생각을 했다.
  

• 그래서 위의 1 1 3 1 2 적용했더니 맞는다.

• 더 나아가서 1 1 3 1 2 1 1 로 햇더니 동일하면 굳이 할필요 없다는 생각을 함.

첫번째 풀이

: resultSum 할 때 int 타입으로 해서 4퍼센트 에서 틀림

두번째 풀이

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 마지막 10000
이라고 하고 n이 100만이라고 하면 resultSum을 long long 으로
변경해야 겠다는 생각을 함.

코드