BOJ 1029 그림 교환

한 그림이 있는데, 그 그림은 산 가격보다 크거나 같은 가격으로 팔아야 하고 같은 그림을 두 번 이상 사는 것은 불가능하다. 즉 그 그림이 어떤 사람의 손을 떠나면 그 사람은 이제 더 이상 그 그림을 소유할 수 없다. 그리고 문제에서 각 사람이 나머지 사람에게 그 그림을 얼마에 팔아야 하는지가 정보로 주어지고, 1번 사람이 가격 0에 그림을 샀을 때, 그 주어진 정보에 따라 최대 몇 명의 사람이 그림을 잠깐이라도 소유할 수 있는지, 그림이 최대 몇 명의 사람의 손을 거칠 수 있는지 구하는 문제이다.

N제한이 15밖에 안되지만, 모든 경우를 다 해보면 N팩토리얼의 시간 복잡도가 될 것 같다.
14팩토리얼만 해도 무려 약 870억 정도... 그렇다면 dp인가...혹시 상태 dp?
2의 15제곱은 32768밖에 되지 않는다.

음 그렇다면, d[n][state] = n번 사람이 그림을 판매할 수 있는 상태가 state일 때, 사람들이 소유할 수 있는 그림의 최대 개수

음 근데, 문제 분류를 보니까 다이나믹 프로그래밍과, 그래프 알고리즘이라고 되어있다.
그래프에서의 다이나믹 프로그래밍 같은데... 다시 고민 좀 해봐야겠다. 그러고 보니 입력 데이터의 형태부터 그래프 입력과 비슷한데... 왜 생각을 못했지 그래프를 그려봐야겠다.

그래프를 그려보니 좀 더 이해가 잘된다. 그래프 상으로는 이동할 때, 1에서 시작해서 점점 더 크거나 같은 경로를 이용해서 이동해야하고, 한 번 방문한 점은 다시 방문할 수 없고 이 때 방문할 수 있는 정점 개수의 최대값을 구하는 문제가 된다.

근데 이렇게 봐도 일단 상태가 필요해보인다. 전에 어딜 방문했고, 어떤 경로를 방문했는지도 알아야할 것인데...결국 상태dp 인건가...
필요한 정보는
1. 현재까지 방문한 경로의 최대값(직전에 방문한 경로) (0~9)
2. 현재까지 방문한 정점 (0 ~ 2의 15제곱-1)

d[node][visitState][pre] = 현재까지 방문한 정점은 visitState이고, 현재 위치 node, 직전 경로의 비용이 pre일 때, 앞으로 방문할 수 있는 정점의 최대 개수

일단 짜보자. 음 비트 AND인 &보다 ==가 연산자 우선순위가 더 높다.
if(state&(1<<i)==0) 여기서 ()괄호를 안 씌워줬을 때 예제 출력이 잘못 나오길래 괄호를 씌워줬더니 제대로 나온다. 제출해 봐야겠다. (if((state&(1<<i)) ==0) 으로 고쳤음)
와 AC받았다... !! 

일단 상태 dp라는 것을 파악했다는 것도 기쁘고, 물론 이 문제의 핵심인 그래프를 이용해야 상태dp로 접근하기 쉽다는 것은 몰랐지만... 이 문제를 교훈삼아 다음부터 잘하면 된다. 그래도 나름 혼자 힘(?)으로 상태 dp문제를 푼 적은 처음인 것 같은데... 기분이 좋다.

하지만 내 시간 복잡도와 특히 공간복잡도가 다른 분들에 비해 매우 크다.
다른 분들 코드 좀 봐야겠다.

음 보고 생각해보니 처음엔 state에 어떤 node를 방문했는지의 정보가 있으니 node를 빼도 되겠다고 생각했는데, 전혀 그렇지 않다. 같은 상태라도 직전에 현재 어떤 node에서 시작하는 건지에 따라 다르기 때문이다. memoization이 안된다.   그렇다면... pre를 빼면 어떨까? pre는 parameter로 넘겨주고 d배열에서는 빼면 어떨까? 그래도 된다. 왜냐하면 현재state에 현재 node만으로 구분이 되기 때문이다. pre가 다르면 어떨까? 현재 state에 현재 node인데 pre가 다를 경우도 있을 것이다. 직전 node가 다를 수 있으니까. 근데 그건 상관없다. 직전 문제기 때문이다. 직전에 어떤 node에서 왔든 현재 상태가 state이고, 현재 node에 있다면 결국 같은 값이 나온다. 직전에 어떤 node에서 왔는지는 (현재 state만 같다면) 앞으로 어떤 node로 갈 것인지에 영향 주지 않는다. 앞으로 어떤 node로, 어떤 경로로 갈지 영향 주는 것은 현재 state와 현재 위치하고 있는 node이 두 가지 뿐이다.
d[node][visitState]

한 번 pre를 제외하고 제출해 봐야겠다!
이럴 수가... 틀렸다. 내가 틀릴리 없어 -> 아 내가 멍청했구나 깨달았다.
pre도 앞으로의 경로에 영향을 준다...!!! 그림은 산 가격보다 크거나 같은 가격으로 팔아야하기 때문에 pre가 뭐냐에 따라 선택할 수 있는 경로(다음 node)가 달라지는 것이다.
음 그렇다면 어떻게 줄이지...? 좀 더 고민해 봐야겠다.

잘 모르겠다... 일단은 내 생각으로는 node, state, pre이 세 가지 요소에 따라 결정되기 때문에 세 가지 요소가 다 있어야 memoization이 가능하다.