[백준 / BOJ] 1029 그림 교환

문제

출처 : www.acmicpc.net/problem/1029

1029번: 그림 교환

사람들이 그림을 사고팔려고한다. 모든 그림 거래는 다음 조건을 만족해야한다.

1. 그림을 팔때, 그림을 산 가격보다 크거나 같은 가격으로 팔아야한다.

2. 같은 그림을 두 번 이상 사는 것은 불가능하다.

 

항상, 1번 사람이 그림을 0원에 샀다고했을때, 그림을 소유했던 사람의 수의 최댓값을 출력하는 문제다.

 

풀이

완전탐색으로 풀면, 최악의경우 첫 선택 = 15명 두번째 선택 = 14명 세번째 선택 = 13명 ... 1명 = 15! 이 돼서 시간초과가 난다.

다이나믹 프로그래밍을 이용해 시간을 줄여줘야하는 문제였다.

 

처음에는 비트마스킹을 이용해 같은 상태를 반복하지않도록 해줬는데, 이렇게 할경우 다른 사람으로 돌아서 왔을때, 더 최소가될수있는 경우를 봐주지못해서 틀렸습니다를 받았다.

dp배열에 사는사람, 파는사람을 같이 저장해줘서, 해당 경로와 상태에 저장된 값보다 현재 값이 더 클경우 반복하지 않도록 해줬다.

dp[현재까지 그림을 소유한 사람][파는사람][사는사람] = 최솟값

 

예를들어, 현재까지 그림을 1번,2번 상인이 소유했으며, 2번상인이 3번상인에게 그림을 팔려할때 최솟값이 2가 저장돼어있다면, dp배열은 

dp[1000000000000011][2][3] = 2 와 같이 저장되어있을것이다. 이때, arr[2][3](초기에 입력받은 2번상인이 3번상인에게 그림을 파는값)에 저장된 값이 2보다 크다면, 탐색하지않고 종료해준다.

 

구현은,

1. dp배열을 초기화 시켜준다. 최댓값이 9이므로, 10이상으로 초기화 시켜주면된다. (이때, 자기자신에게 그림을 사고팔수없으므로, 사고파는 사람이 같을경우 0으로 초기화시켜준다.)

2. 탐색을 시작하는데, 이때 사고파는 사람이 같을때, 산가격보다 더 작은 가격에 팔려고 할때, dp[다음사람에게 팔았을때 상태][현재 파는사람][다음에 사는사람] <= 현재 파는 가격 이라면 리턴한다

 

위 과정을 반복하면서 최댓값을 찾아 출력하면 된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1029%20%EA%B7%B8%EB%A6%BC%20%EA%B5%90%ED%99%98/main.cpp

devxb/JJUNalgo