[platinum3][해설안봄 , 분류확인] 8902 색상의 길이

https://www.acmicpc.net/problem/8902

 

오랜만에 글을 작성한다.  일주일전에 풀었던 문제다. 사실 주말부터 어제까지 16880 룩, 비숍, 킹, 나이트, 궁전 게임을 몇일 간 고민하다가 게임의 필승조건이 너무 복잡하고 도저히 못 풀겠어서 분류를 확인한 결과 게임이론 + 특정 알고리즘이 더해진 문제였다.. 자괴감이 들지만한편으로는 그렇게 시간을 부어도 못  푼 원인이 내가 규칙을 못찾아서가 아니라는 것에 안도감을 느꼈다. 

실전 연습하다가 잠깐 도파민 충전용으로 도전해보자 한 문제를 몇일 간 질질 끌었으니.. 참 나도 어지간히 집요하다. 진짜 안되겠으면 끊어내는 것도 용기인것을.. 사실 알고리즘 문제뿐만 아니라 일상에서도 마찬가지다.. 이런 성격이 도움이 될때도 있지만 치명적인 시간, 효율 낭비와 심각한 정신적 데미지를 동반할 때도 있기때문에.. 절제하는 능력도 중요한 것 같다.

 

각설하고 이 문제또한 오랫동안 질질 끌었던 문제였다.  아이디어는 그렇게 복잡하지는 않지만 구현하는게 많이 낯설고 빡세서 디버깅하는데 얼마나 걸렸는지,, 분류확인 후 순수 DP문제 인걸 확인하고 안심하고 들어갔다가 실컷 두들겨 맞았다/

 

 

차량이 이렇게 있을 때 아랫줄 차량의 순서를 유지하며 윗줄에 끼어넣든, 윗줄을 아랫줄에 끼어넣든 같으므로, 아랫줄을 위에 껴넣는 걸로 생각하고 문제를 풀었다.

dp[윗줄의 i번째 차량] [ 아랫줄의 j번째 차량] = L(c) 총합의 최솟값 으로 둔다.

이 문제의 핵심은 차량이 끼어들때 L(c)가 누적합처럼 증가할 수 있다는 거다.

 

위처럼 y5가 b3, r6사이에 끼어들땐, 노랑,파랑,초록의 L(c)가 1 증가하게 된다. 반면 빨간색의 L(c)는  증가하지 않게 된다. (빨간 차중에 맨앞, 맨 뒤에 있는 차 사이에 끼어들지 않기 때문에).

 

이제 b3 ,r6사이인 4 번 다음 인덱스인  5번 index에 끼어들게 된다면, 빨간색 차까지 L(c)총합에 추가되어  L(c)의 누적합은  + 1 증가하게 된다.

 

그런데 이문제의 어려운 점은 수많은 조건의 분기가 있다는 것이다. 

위의  끼어넣을 자리의 index를 i1,  끼워넣을 차의 index를 i2 라 하고 둘의 조합을 (i1, i2)라 할때,  (3,1), (4,1), (5,1) (노랑차 끼워넣기)은 노랑의 L(c)를 1씩 증가시키 지만, (0,1), (1,1), (2,1) 과 같은 경우에는  노랑차의 맨앞을 결정하기 때문에 끼워넣기가 아니다.  즉  노랑의 L(c)는 원래 3이고, i1: (3,4,5)번에 끼워넣을 때는 L(c)가 4가 된다.   그러나 i1 : 0번에 들어간다면 L(c)는 6이 될 것이다.  

그렇다면 이걸 어떻게 dp에 적용할까? 먼저 일주일전에 풀었던 방식이다.   끼워넣기가 아닌 맨앞을 결정짓는 위치라 할때  그 위치만큼 뺀다.  그 리고 나중에 맨뒷차를 결정짓게 될때  그 위치만큼 더한다. 

 예를 들어

이런식으로 첫차는 인덱스가 2, 마지막 차는 7 로 들어가므로   L(c)는 -2 + 7 = 5 가 된다. 물론 끼워들게 되면서 인덱스 조정이 필요해 실제 L(c)는  5 + 1 = 6 이 되지만 원리는 이렇다.

 

그런데 그냥 지금 풀이를 쓰다보니 미리 노랑 L(c)를 구해놓고 (3),   맨앞이 바뀔 때 원래 맨앞 차의 인덱스 차이만큼 더하는게 더 깔끔할 것 같다.

이런식으로.. 즉 맨앞이 업데이트 될때 L(c) = 3 + 1 = 4 ,   맨뒤가 업데이트될때 L(c) = 4 + 2 = 6  이 될 것이다.

 

어쨌거나 이렇게 맨앞이 업데이트 될때의 이슈를 해결하였다.

 

맨앞이 갱신될 조건은 무엇일까?   밑줄의 맨앞차를 윗줄의 맨앞차보다 앞에 둘 때이다. 

위처럼 밑줄의 노랑차가 맨앞, 맨뒤 사이에 한대가 더있다고 생각해보자.   이렇게 밑줄에서 맨앞, 맨뒷 차 사이에 있을 때는 i1의 어디에 배치하던 끼워넣기가 되어 L(c) += 1 이 된다.

밑줄의 맨앞차가  윗줄로 들어갈때 맨앞을 갱신할수도 없을 수도 있다. 맨뒷차도 마찬가지.  그러나  가운데 차(노란네모속의 차)는 i1의 어디에 들어가든  앞에는 1번차, 뒤에는 8번차가 있기 때문에 끼워넣기밖에 할수 없다. 따라서 1번 ~8번 사이에 있는 노란차는 무조건 L(c) += 1  이 된다.

 

맨뒷차(8번 차)는 맨앞차와 마찬가지로 윗줄에 끼었을 때 맨뒤를 갱신하거나 끼워들어갈(L(c) += 1)수 있다.

 

정리하자면 i2의 포지션, i1의 포지션에 따라 위와 같이 될 수 있다. 

이렇게 케이스 분류를 해보았고, 

dp최적화를 위해 그리디도 생각해야 한다.

 

dp[i1][i2] 에서  i2가 같을 때 i1이 증가할 수록 dp 값은 작아지거나 같아야 한다. 

dp[2][1] , dp[3][1] 을 비교해보자. 전자는 밑줄1번차가 i1: 2번으로 낄 때, 후자는 1번차가 i1 3번으로 낄 때다. 

dp[2][1] 은 1번차가 2번에 들어갔다는 뜻으로, 그다음차(빨강차)는 3~9번까지 끼어들 수 있다. 

반면 dp[3][1]일때는 3번에 들어갔으므로 다음차는 4~9번까지밖에 못들어간다.

즉 i1이 증가할수록 다음차가 들어갈 수 있는 범위가 줄어들므로, 불리하다.  불리하므로, dp값이라도 작아야 한다. 

불리한데도, dp가 이전값보다 큰 상황은 용납할 수 없기 때문이다. 

 

따라서 dp[1][1] >= dp[2][1] >= dp[3][1] ...  이다.

반복문 순회는 i2의 반복문 안에 i1이 순회하게 된다. O(N ^2).

dp[5][4]  의 경우를 생각해보자.    3번차L(c)합 에  4번차량에서의 변화량만큼 더하면 된다.   3번차가 i1: 0,1,2,3,4,5번에 낄때중 L(c)합 이 최소일때를 구해야 한다. 근데 방금  dp[1][1] >= dp[2][1] >= dp[3][1]>=dp[4][1] >=dp[5][1] .. 이라했으므로,  5번에 낄때가 최소값이다.

따라서 dp[5][4] = dp[5][4] + 변화량 이다.  

변화량의 누적합을 sum[i1] 이라 하면, sum[4] 에서 sum[5] 로 갈 때는 빨간차의 중간에 새로 끼게 되므로 sum[5] = sum[4] + 1 이다. 이런 누적합으로 불필요한 계산생략이 가능하다.

dp[5][4] = dp[4][4] + (3 + 1) 이 된다.

 

 

계산은 이와 같이 하면 된다.

또 실수하기 쉬운 부분은 누적합을 계산할 때 자기와 같은 색깔의 차에 대해선 적용하지 않는 다는 것이다. 같은 색깔의 차에 대해선, 아래에서 했던 것처럼 여러 조건을 분기해 따로 처리해야 하기 때문이다.

 

여러모로 구현하기가 복잡하고 힘들었던 문제였다...