[platinum4][풀이, 분류 미확인] 34059 해안선

굉장히 고전했던 문제였다.

처음엔 dp를 생각했지만,  N 이 너무 방대했고, 결국 알고보니 nCm 조합으로 구할 수 있었다. 여러 경우를 따져가며 풀이하면 되는데 좀 많이 까다로웠다. 체감상 플레2~3정도 ㅜㅜ

 

우선 1번 부터 교차하지 않는다는 것에 유의하며 진행해보자. 처음엔 아래와 같이 시작하고

그후엔 다음과 같이 진행할 것이다.  1 ~2번 을 방문했으면       1번의 왼쪽인 7번 or  2번의 오른쪽인 3번으로  갈 수 있다.

그럼 다음은 아래와 같이 진행된다.

즉 방문은 무조건 지금껏 방문한 곳의 맨왼쪽의 왼쪽 or 맨오른쪽의 오른쪽 만 방문할 수 있고, 방문한 곳은 연속적이게 된다.

 

여기서 관찰을 잘 해보면 , 항상  맨왼쪽 왼쪽 or 맨오른쪽 오른쪽으로 방문하게 된다.  (6,7,1,2 번 방문했을 때 -> 5번 방문 or 3번 방문)

 

그렇다면, 왼쪽으로 범위를 넓히거나 , 오른쪽으로 범위를 넓히는 것이므로,  다음과 같이 생각할 수 있다.

 

만약 (5,6,7,1,2)번을 방문했다고 치자. 그렇다면 , 왼쪽으로  3칸, 오른쪽으로 1칸을 확장시킨 셈이 된다.  그럼 다음 그림과 같이 생각할 수 있다.

왼쪽 화살표는 왼쪽 확장, 오른화살표는 오른쪽확장 이다. 여기서 화살표의 순서는 바뀌어도 상관없다. 위의 두가지 경우 모두 가능하다는 뜻이다. 여기서는 경우의 수는 4C1  or 4C3 이 될 것이다.    

즉 L 3 R 1 -> 4C1 의 경우의 수로 나타낼 수 있다. 

 

간단하게 표현하면 1번부터 왼쪽으로 n1번 떨어진 곳 ~ 1번부터 오른쪽으로 n2번 떨어진 곳  까지 방문하는데는

n1 + n2 C n1  이 되는 것이다.

 

지금까지 저걸 구한 이유를 이제 설명하려고 한다.

 

우선 특정 도로를 반드시 방문한다고 할 때 , 두가지 경우로 나눠야 한다.

 

1. 도로가 n번  -> n + 1번 인 경우 :

 

     먼저 어떤 도로를 지나가야 한다는 조건 없이 k번으로 방문을 종료하려고 할 때 ,어떻게 구해야 할지 생각해보자.

 

k = 4 번일 경우,  

 5,6,7,1,2,3 번까지 방문하는 경우의 수는 L : 3 , R : 2  로 5C2 이다. 이때 중요한 것은 이렇게 방문했을 때 마지막 방문한 곳이 3번또는 5번이라는 것이다.  그러나 3번에서 4번으로 가든,  5번에서 4번으로 가던  모두 가능하다. 따라서  1번에서 시작해서 4번으로 끝나는 경우의 수는 5C2 = 10 이다.

이걸 미리 설명한 이유는 아래에서 계속된다.

 

4 -> 5번이 필수 경로인 경우, 이 경로를 그냥 하나의 점으로 취급해 보자. (이 아이디어는 매우 중요하다. 이걸 생각하지  않아서 수많은 경우의 수를 생각하며 애를 먹었다.)

 

 

그럼, 여기서 1번부터 모든 경로를 방문하고,  점 4,5(합쳐짐) 으로 끝나는 경우를 생각해보자.  

아까 설명한 대로  이번경우는 L : 2 , R : 2 이므로 4C2 경우의 수다.

근데 유의 할 점은 4,5번을 한점으로 생각했는데,  경로가 4->5 가 될 수도 있고,  5-> 4  가 될 수도 있다.  따라서 점4,5로 끝나는 경우, 즉 도로4,5번이 마지막 거치는 도로일 경우...  경우의 수는 4C2  * 2 (4->5 or 5 ->4) 이다.  다시 한번 강조하지만, 이렇게 점으로 취급하지 않으면 상당히 복잡해진다. 여기에 몇시간을 썼는지..

 

또 다른 경우도 있다.  4,5 로 끝나지 않고 다른 점으로 끝 날 수도 있다.   이 경우를 잘 생각해보자. 다른 점으로 끝나더라도, 점4,5는 지나므로 즉, 필수도로는 지나는 것이다.  만약  3 -> 4,5 -> 6 번 순으로 지나갈 경우   필수도로에선 4 -> 5 순으로 지나갈 것이고,  6-> 4,5 -> 3 의 경우 5->4 순으로 지나 갈 것이다. (다시 강조하지만 점으로 생각안하면 매우 복잡해짐)

그럼 다른 점으로 끝나도 필수도로는 지나는 것으로 안심하고, 1번을 제외한 모든 점에서 끝날 경우를 생각해보자.

 

2번으로 끝날 경우,  L : 4 , R : 0

3번으로 끝날 경우,  L : 3 , R : 1

4,5 번으로 끝날 경우 L : 2 , R : 2

6번으로 끝날 경우,  L : 1, R : 3

7번으로 끝날 경우,  L : 4 , R : 0

 

다합치면 4C0 + 4C1 + 4C2 + 4C3 + 4C4 가 된다.

근데 어디서 많이 봤지 않은가. 바로 저 값은 2 ^ 4 가 된다.  즉,   (왼쪽 or 오른쪽 ) ^ 4  의 경우의 수를 따진 셈이다.

그럼 2~7번으로 끝나는 경우 2 ^ 4 이다.     근데 한가지를 더 생각해야 한다. (4,5) 로 끝나는 경우는  2를 곱해야 한다.

아까 처럼 4->5, 5->4 의 경우가 있기 때문이다. 다른 경우는 예를 들어 3->4,5 ->6 을 지날 때는 필수도로를 지나는 방향이 정해지므로 (4->5) 그대로이다.   

결국  4C0 + 4C1 + 2* 4C2 + 4C3 + 4C4   = 2 ^ 4 + 4C2 가 된다.

 

자 이렇게 복잡해 보이지만 간단하게 표현 할 수 있다.  간단하게 표현하면  2 * (N - 3) + (R+L)C(L) 이 된다.

 

2. 필수 도로가 n-> n+ 1이 아닐 경우, 즉 바로 다음 지점으로 이동하지 않는 경우

 

다음 경우도 생각해보자.

 

 

만약 3-> 6을 지나는 필수도로일 경우, 3,4,5,6을 한점으로 취급한다.

매우 중요한 점은 이번에는 방문할 때 반드시 점 3,4,5,6,7,8 을 끝으로 방문을 마쳐야 한다는 거이다.

  1->9->3,4,5,6,7,8>2 처럼 2번으로 끝내려고 하는 경우,  필수도로는 8->3 으로 지나게 되는데 ... 이때  3->2 로 가게 된 후 4번 , 5,6,7번을 방문하려고 하면 도로가 교차하게 된다.     만약 8->3을 지나고,  4,5,6,7을 지나고 2번으로 가려고 하는 경우도 도로가 교차하게 된다.

 

그렇다면  , 3,4,5,6,7,8으로 끝나는 경우, L : 1 R : 1 -> 2C1 의 경우의 수를 갖게 된다.

문제는 이제 3,4,5,6,7,8 번을 방문한 후,  나머지 4, 5,6,7번을 어떻게 할 것이냐는 것이다.

이 경우는 발상의 전환이 필요하다.

위와 같은 경우를 보자.    눈치가 빠르다면 바로 알아차릴 수도 있는데  위와 같이7,6,5,4 를 방문하고, 5번으로 끝나는 경우 

마지막 끝점 5번을 시작점으로, 7,6,5,4 번을 방문하게 하는 것과 동치이다. (역으로 진행) 

즉 , L : 2 , R: 1 로 3C1 의 경우의 수이다.  

7번을 시작점으로 하는 경우 -> L : 0 , L : 3

6번을 시작점으로 하는 경우 -> L : 1 , L : 2

5번을 시작점으로 하는 경우 -> L : 2 , L : 1

4번을 시작점으로 하는 경우 -> L : 3 , L : 0

 

어떤 점으로 시작하든 4 or 7로 끝나게 된다.     경우의 수는 3C0 + 3C1 + 3C2 + 3C3= 2^3 이다. 기가막히지 않은가.,

만약 7로 끝날 경우, 즉 위의 그림과 같은 경우 필수도로는 8->3 ->7 or 3->8->7 로 진행할 수 있다.  4로 끝나도 마찬가지이다.  따라서 경우 수에 2를 곱해야 한다.

 

그럼 최종적으로  

 2C1 ( 점 3,4,5,6,7,8 까지 이동) * (2 * 2^3 (4,5,6,7 번 방문 처리) )  = 2 * 2 * 8 = 32

 

간단히 하면 (L + R)C(R) * 2 * 2^(필수도로 밑의 점의 수 - 1) 가 된다.

 

최종적으로,

 필수도로가 바로 다음 도시일 경우 : 2 * (N - 3) + (R+L)C(L) 

 아닐 경우 : (L + R)C(R) * 2 * 2^(필수도로 밑의 점의 수 - 1)

 

 

결과는 매우 간단하지만, 과정이 너무 힘든 문제였다. 이게 왜 플레 4 일까..

참고로,  최대 100만자리 수에서 조합을 구하자니, 너무 귀찮아서 (L + R)C(R)을 구할 때는 페르마의 정리를 활용해 구했다. (gpt복붙..)

AI시대에 아이디어는 인간이 내고, 전형적인 구현은 AI가 구현해주는게 당연하지 않을까 하며 자기 합리화 하며..