BAEKJOON_11052) 카드 구매하기

BAEKJOON 

# 알고리즘 기초 # 2019 SW역량테스트준비-기초

# 다이나믹 프로그래밍 

11052) 카드 구매하기 (19.03.19) (19.09.27)

* 그 전 값에 어떻게 더하느냐에 따라 구하고자 하는 값이 여러개가 나왔고, 그 중 가장 큰 값을 골라 출력했다.

* 처음에는 구하고자 하는 경우의 3가지 전까지만 고려했는데,
* 반례를 살펴보니 구하고자 하는 순서의 절반까지는 생각해주어야 했다.

* 그렇기 때문에 j 의 값을 1부터 i/2 까지로 정했고, 그 값들 중 최대값을 찾았다.

* 이 문제는 강의에서는 붕어빵 판매하기 였는데, 문제가 달라 질문하기를 살펴보니 바뀌었다고 했다.

* 채워야 하는 칸의 수는 n 개,
* 그리고 한 칸을 채울 때 마다 1부터 i/2 까지 돌아봐야 하기 때문에 O(N)
* 따라서 시간복잡도는 n*O(N), 즉 O(N^2) 이다.