dovelet - 옥상1 - 색상 환/color_circle

http://183.106.113.109/pool/color_circle/color_circle.php?pname=color_circle

N개의 원형배열에서 K개의 index를 인접하지 않게 선택할 수 있는 경우의 수를 구하는 문제.

콤비네이션을 이용하여 간단하게 풀 수 있지만 다이나믹 프로그래밍을 이용하여도 된다.

처음에는 N만을 이용하여 나올 수 있는 모든 경우의 수를 확인하였다.

N - 1
1

N - 2
01
10

N - 3
010
100
101
001

N - 4
0100
1000
1010
0010
0101
1001
0001

...

수식으로 표현해주면 'arr[n] = arr[n - 1] + arr[n - 2] + 1' 이다.

그러므로 N이 좀만 높아지게 되면 64비트형 데이터타입으로도 표현할 수 없는 크기의 경우의 수를 가지게 된다. 당연히 모든 경우의 수를 개별적으로 관리하는것도 비효율적이 된다.

그래서 K가 같은것끼리 통합하여 끝자리가 0인지, 1인지만 구별하여 관리하도록 하였다.

N - 1
   1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0

N - 2
   1 2 3 4 5 6 7 8 9
0 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0

N - 3
   1 2 3 4 5 6 7 8 9
0 2 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0

N - 4
   1 2 3 4 5 6 7 8 9
0 3 1 0 0 0 0 0 0 0
1 1 2 0 0 0 0 0 0 0

...

하지만 위의 동적배열은 원형상태의 경우의 수가 아니라 처음과 끝이 만나지 않는 경우의 수를 저장하고 있는 동적배열이다.
즉, N이 4일때 K가 2라면 1001은 처음과 끝이 만나므로 계산에 포함하지 말아야 한다.

이 처리는 동적배열을 채워나가면서 중간에 'N - 4' 일때 'K - 2' 값을 미리 저장해놓으면 된다.

그리고 결과값에 저장해준 값을 빼주면 된다.

슈도코드는 다음과 같다.

arr[1][0] = 0;
arr[1][1] = 1;
for i in (1 to N) :
    for j in (N / 2 to 1) :
        arr[j + 1][1] = arr[j][0];
        arr[j][0] = arr[j][0] + arr[j][1];

    if (i == N - 4)
        tem = arr[K - 2][0] + arr[K - 2][1];

result = arr[K][0] + arr[K][1] - tem;