[백준 / BOJ] 2313 보석 구매하기

출처

풀이 : www.acmicpc.net/problem/2313

2313번: 보석 구매하기

보석가게에 보석이 여러줄에 걸쳐 진열되어있다. 각각의 보석은 정수로 표현된다. 이때 음수도 나올수있다.

 

보석은 연속해서 구매할수있는데,

1 2 3을 구매할수있지만, 

1 3 을 구매하지 못한다. 

보석 가치의 총합이 최대가 될때를 찾아는 문제다.

 

풀이

한줄당 최대 1000개의 보석이 있을수있고, 최대 1000개의줄이 나올수있다. 따라서 최대 보석은 1000000개 만큼 나온다.

한줄당 연속해서 구매하는 보석의 조합을 모두 봐줘야하므로 완전탐색으로 풀경우 시간초과가 난다. 

 

DP로 풀어야하는 문제였다.

 

1차원 dp[]배열을 선언한다. (dp[idx] = left에서 right까지 더한값)

left, right는 구매한 보석의 왼쪽 ~ 오른쪽이다.

 

알고리즘은

보석의 가중치가 arr[idx]에 저장되어있을때

arr[idx]에 있는값이 dp[idx-1] + arr[idx]보다 크거나 같다면, dp[idx]를 arr[idx]로 초기화 시키고 left와 right값도 바꾼다.

아니라면 dp[idx]에 dp[idx-1] + arr[idx]를 저장하고 right값을 +1해준다.

 

예외처리를 해줘야했는데,

 

보석이

100, 100, -201, 1, 1 이렇게 주어졌다면, 3번보석까지 구매했을때 보석의 가중치는 -1이되서 4번보석을 구매할때 left와 right가 4 4로 초기화 된다. 이렇게 되면 마지막에 4 5가 출력되는데, 1 2 보석을 구매했을때 200이 출력되어야 하므로 예외처리를 해줘야한다.

난 pair를 2중으로 선언해서 최댓값을 저장해주는식으로 예외처리해줬다.

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2313%20%EB%B3%B4%EC%84%9D%20%EA%B5%AC%EB%A7%A4%ED%95%98%EA%B8%B0./main.cpp

devxb/JJUNalgo