[알고리즘 문제] 1146번 지그재그 서기

출처 : https://www.acmicpc.net/problem/1146

 

1. 접근

1. 키(숫자)는 궁금하지 않다, 즉 (1 2 3 4) 나 (1 5 7 9) 는 같은 상태이다.
2. 모든 키가 다르므로 결국 인원 수가 중요하다
3. 가장 키가 큰 N을 어디에 배치할지 정하고 나눠진 구간을 subproblem 으로 계산하자!

 

 

처음부터 위와 같이 접근한 이유는 다음과 같습니다.

1. 상태의 독립성을 나타내기 위한 정보는? -> "인원수"
2. subproblem 으로 쪼개고 싶다! -> (3)

 

 

2. 고찰

N을 배치함에 따라 left, right 영역으로 나눠진다고 할 때 다음과 같은 궁금증이 떠올랐습니다.

dt[N] : 지그재그 서는 가지수라고 하고 ( left ) N ( right ) 꼴로 나타날 때,

Q. left의 가장 오른쪽 부분이 증가하는 꼴이였다면? 
ex) 2 1 3 (N) (right) 

 

위의 궁금증을 해결하고자 가장 왼쪽이 증가/감소 하는지를 dt로 나누고자 계획하였습니다. (2차원 dt) 그 과정에서 N이 홀수, 짝수일 때 특징을 고민하다가 지그재그 모양을 머리속에 그리게 되었고...

 

 

3. 정답으로 다가가기

N이 짝수든 홀수든 결국에는 "대칭 변환" 을 하면 가장 오른쪽 혹은 왼쪽 부분의 증가/감소를 결정할 수 있지 않을까? 생각하였고 1) 2) 를 통해 확신을 가지게 되었습니다.  

 

즉, 지그재그를 좌우/상하 반전으로 특정 부분을 감소/증가로 나타낼 수 있기에 /2 연산만 해주면 됩니다. 추가적으로 위에서 인원수만 중요하다고 언급했지만 그것은 dt에 저장할 때 독립을 따지기 위한 요소이며, 계산할 때 조합을 사용하여 경우의 수를 나타내야 합니다.

 

 

4. 실수하기 쉬운..

확신을 가지고 구현을 하는데.. 원하는 결과가 나오지 않았고 디버깅을 통해 대칭 변환을 고려하기 위한 나누기 연산을 dt[1] 에 적용하면 0이 되어 원하는 결과가 나오지 않은것을 알 수 있습니다. 

 

논리적으로 볼 때 N = 1 인 경우 그 자체가 감소/증가를 따질 수 없기에 예외케이스로 적용해줬습니다.

 

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000;
int N, dt[105], pascal[105][105];


int main()
{
    cin>>N;
    dt[0]=1, dt[1]=1, dt[2]=2;
    for(int i=1;i<=N;i++){
        pascal[i][0]=pascal[i][i]=1;
        for(int j=1;j<i;j++) pascal[i][j]=(pascal[i-1][j-1]+pascal[i-1][j])%MOD;
    }

    for(int i=3;i<=N;i++){
        for(int j=1;j<=i;j++){
            int l=j-1, r=i-j;

            dt[i] += ((long long)pascal[i-1][l]*((long long)(dt[l]+1)/2)*((dt[r]+1)/2)%MOD)%MOD;
            dt[i] %= MOD;
        }
    }
    cout<<dt[N];
}

 

pascal 은 nCr 을 나타내기 위해 파스칼 삼각형을 만들었습니다. 다음으로 아래 점화식 (dt + 1) / 2 의 의미에 대해 알아보겠습니다.

 

+1 의 의미)
dt[1] 을 나누기 연산할 때 0이 되는 것을 막기 위함입니다. 위 문제에서 dt[1] 후에는 대칭성에 의해 항상 짝수임을 알 수 있기 때문에 +1 로 예외처리를 진행했습니다. 

/2 의 의미)
위에서 언급했듯이 대칭성을 통해 특정 부분의 증가/감소를 결정시켜주기 위함입니다.

※ 참고
+1 대신에 dt[0]=dt[1]=2 로 진행하여도 문제가 되지 않습니다.

 

 

5. 확장해보자!

위 문제는 운이 좋게도 MOD 가 짝수여서 /2 연산을 진행하여도 되지만 보통 그렇지 않은 경우가 많기에 약간의 수정이 필요합니다. 문제가 생기는 까닭은 홀수를 나누는 경우에 불분명하기 때문입니다. 따라서 아래와 같이 수정하면 됩니다

update)
pascal, dt 업데이트 부분에서 % (MOD * 2) 로 진행

output)
정답을 출력할 때 % MOD 진행하여 출력

 

 

---

 

이번에는 바로 아이디어를 세우고 쉽게 풀어봤는데요.. 이전에는 위처럼 분석하는 시간이 짧았던 것 같습니다. 그리고 아직도 "통일성 있는 코드" 를 집착하다 보니 "예외처리" 를 하면 틀린 코드, 논리가 떨어지는 코드라고 생각하는 버릇이 남아있는 것 같습니다. dt[1] 을 나누기 연산할 때 예외로 처리한 것이 아직은 자연스럽지 않다고 느껴지지만.. 앞으로 많이 풀어봐야할 것 같습니다.