[BOJ 27533] 따로 걸어가기

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

27533번: 따로 걸어가기

오래간만입니다. 리유나입니다. 어쩌다보니 한번 손을 놓게 된 뒤로 또 포스팅을 한참 못하게 되더라고요... 시험도 끝난 김에 뭐라도 다시 글을 올리려고 최근에 풀었던 조합론 문제를 하나 소개하려고 합니다!

 

SUAPC 2023 Winter L번으로 나온 문제라고 하네요. 문제의 설명은 꽤나 귀엽고 재미있는데, 대강 요약하면 N*M 격자 위에서 최단경로로 이동하는 경우의 수를 구하는 문제입니다! 다만 여기서 조건이 추가로 붙는데, 토순이와 토준이가 크게 싸운 탓에, 출발점과 도착점을 제외한 곳에서는 경로가 겹쳐서는 안됩니다.

1. 어떻게 생각해야 할까?

배경지식이 어느 정도 있으시다면, 아마도 카탈란 수열과 비슷한 문제 아닐까? 하는 생각을 떠올리실 수 있습니다. 카탈란수가 무엇인고 하면,

출처: 한국어 Wikipedia "카탈랑 수" 항목

다음과 같은 식으로 정의되는 수열입니다. 그냥 그런 수열 아닌가? 싶으시겠지만 이게 정말 조합론 기초에서 잊을만하면 어디선가 튀어나와요... 정말 신기하게도.

 

간단하게, 다음과 같은 문제를 한번 생각해볼까요?

 

당신은 영화관의 카운터 직원입니다. 아무래도 영화관에서 현금이 긴히 필요했는지, 이 시대에는 도무지 믿기지 않을 가격인 영화 한편 5천원에 티켓을 팔고 있습니다! 다만, 현금 결제만 가능합니다.

2n명의 사람들이 영화를 보러 왔습니다. 그런데 이 사람들 중 절반은 5천원짜리를 들고 왔지만, 나머지 절반은 만원짜리만 가지고 있습니다. 오천원을 거슬러 받아야만 표를 살 수 있는 상황이네요.

그런데 카운터에는 거스름돈으로 줄 돈이 한 푼도 없습니다! 이때 무사히 영화표를 다 팔 수 있을 확률은 어떻게 될까요?

 

이 문제는 사실 "2n의 길이를 가진 올바른 괄호 문자열의 개수는 몇 개가 되는가?"하는 문제와 완벽히 같음을 알 수 있습니다! 그리고 그 정답은 놀랍게도 C_2n입니다. 이걸 흔히 설명할 때, 다음과 같은 문제로도 바꾸곤 합니다.

그림을 좀 깔끔하게 만들고 싶었지만, 그냥 대충 알아보시리라 믿습니다.

A에서 B까지, n*n 격자를 통해서 최단거리를 갈 것인데, 이 과정에서 대각선을 넘어가지 않는 경로의 수는 몇 가지인가? 하는 문제로도 바꾸어서 생각할 수 있습니다. 오른쪽으로 가는 걸 5천원을 받는 것, 위로 가는 걸 1만원을 받는 것으로 생각하면 대강 느낌이 올 겁니다.

점화식을 잘 세우거나, 최초로 대각선을 넘어간 경로 이후를 반전시켜서 n-1*n+1 격자로 치환시키는 등의 방법을 사용하면 이 경우의 수가 C_n과 같음을 알 수 있습니다.

 

이쯤 오면, 우리가 처음으로 이야기했던 토끼가 다시 생각날 겁니다. 뭔가 넘어가면 안될 선이 있고, 격자를 따라 최단 거리..? 라는 점에서 유사성을 찾을 수 있는데요, 문제의 상황이 다소 다르기 때문에 바로 카탈란이 나오지는 않지만, 어느 정도의 아이디어는 유사할 것을 짐작할 수 있습니다. 그리고 그 짐작은 정확합니다.

 

2. 어떻게 풀어야 할까?

(*이 부분에서 논리를 정리할 때 공식 풀이 슬라이드를 다소 참고했습니다.)

한 단위 시간이 지날 때마다 일어나는 이동을 편의상 다음과 같이 정의해 보겠습니다.

 

1. 토순이, 토준이가 모두 오른쪽으로 움직인다.

2. 토순이는 오른쪽, 토준이는 아래쪽으로 움직인다.

3. 토순이는 아래쪽, 토준이는 오른쪽으로 움직인다.

4. 둘 모두 아래쪽으로 움직인다.

 

그리고, 생각해보면 처음부터 1번 혹은 4번 이동을 하면 기껏 싸워놓고 바로 같은 길로 가는 뻘쭘한 상황이 벌어지기 때문에, 결국 경우는 2/3으로 시작할 수밖에 없다는 걸 알 수 있습니다. 비슷한 이유로, 마지막도 3/2로 끝날 수밖에 없습니다. 일반성을 잃지 않고, 맨 처음에 토준이가 오른쪽, 토순이가 아래쪽으로 이동했다고 가정해봅시다.(즉, 3번 이동부터 시작한다는 이야기입니다.)

 

짐작하셨겠지만 모두가 아래/모두가 오른쪽으로 움직이는 연산이라 해봐야, 이미 안 만나 있으면 몇번 더 한다고 다시 만날 일은 없습니다. 핵심이 되는 건 2번/3번 연산이 되겠네요. 어느 순간에든 간에 토순이가 토준이보다는 많거나 같은 횟수만큼 아래쪽으로 갔어야 합니다.(만약 그렇지 않다면, 역전되는 순간에는 무조건 둘이 마주쳤을 수밖에 없기 때문입니다.)이를 위해서는, 처음 3번 이후, 마지막 2번이 오기 전까지 어떤 시점에서도 2번이 3번보다 많아질 수는 없다는 이야기입니다.(맨처음 이동은 빼고 세면, 같은 것까지는 괜찮습니다.)

 

어떤 시점에서도 뭐가 뭐보다 많아지지 않는 수열?

->괄호 문자열?

->극장 표?

->카탈란?

 

네 맞습니다. 여기서 2번과 3번 이동의 횟수가 정확히 같아야 하고(구체적으로는, min(n, m)-2를 넘길 수는 없습니다.)각각의 경우에 대해서 이게 정해지면 1번과 4번 이동이 몇번인지도 자동으로 정해집니다. 2번과 3번의 이동 횟수가 정해졌을 때의 경우의 수는 C_n으로 바로 구할 수 있고, 그 사이사이에 4번과 1번을 어떻게 잘 넣을 수 있을지, 그걸 중복조합으로 계산하면 됩니다!

 

마지막으로, 맨처음에 일반성을 잃지 않고 토준이를 오른쪽으로 보냈기 때문에, 정반대의 경우도 생각하기 위해서 *2를 해주면 답이 완성됩니다.

3. 구현/Python 3

n,m=map(int,input().split())
mod = int(1e9+7)
fact=[1]
for i in range(810000):
    fact.append(fact[-1]*(i+1)%mod)
def c(n): #카탈란 수 구현
    res=fact[2*n]
    res*=(pow(fact[n], mod-2, mod)**2)%mod
    res*=pow(n+1, mod-2, mod)
    res%=mod
    return res

def solve(n, m):
    if n==m==2:return 2
    res=0
    if n>m:n,m=m,n
    for i in range(n-1):
        a=n-2-i
        b=m-2-i
        ct=fact[n+m-4]*pow(fact[a], mod-2, mod)*pow(fact[b], mod-2, mod)*pow(fact[i*2], mod-2, mod)
        ct%=mod
        res+=ct*c(i)
        res%=mod
    return res*2%mod

print(solve(n,m))

 

코드 복사/붙여넣기 하는 당신이 아름답습니다. 로직 정도만 참고해주세요.

마지막 부분 설명이 조금 얼버무려졌는데, 이 부분을 제대로 이해하려면 중복 조합에 대한 이해가 있으면 좋습니다. 고등학교 수학 확률과 통계 앞단원쯤에서 지겹게 나와서 수험생들을 괴롭히는 내용이고, 이에 대해서는 나중에 따로 포스팅해보거나 하겠습니다.