BOJ 2482(색상환)풀이

solved.ac 티어 : 골드 4

www.acmicpc.net/problem/2482

2482번: 색상환

이 문제는 코드업의 극장 좌석 배치 2를 풀고 하면 쉽게 할 수 있다.

codeup.kr/problem.php?id=2652

극장 좌석 배치 2

이 문제와 색상환의 다른 점은 색상환은 양끝이 이어져있다는 것이다.

색상환은 코드업 문제에다가 한 가지 경우의 수를 빼주면 되는데 그건 바로 양끝이 선택됐을 경우이다.

색상환은 코드업 문제와는 다르게 양 끝이 만나면 안 된다. 그러므로 코드업문제에서 양끝이 모두 선택되어있고 나올 수 있는 경우의 수를 빼주면 된다. 양끝이 선택되어있고 나올 수 있는 경우의 수는 어떻게 구할 수 있을까?

 

바로 양쪽 2개를 지워주고 코드업문제 코드를 돌리면 된다. 그 이유는 양끝 값이 선택되어있다면 그 옆칸은 선택할 수 없기 때문에 양쪽으로 2개를 지워주고 k에도 -2를 해준 다음 코드를 돌리면 된다.

양쪽 2개를 없애준다면 나머지에서는 양쪽에 값이 있어도 되기 때문이다.

 

from math import factorial as t
a=int(input())
b=int(input())
if b==1:print(a)
else:
    c=a-b
    d=max(0,a-4)
    e=max(0,b-2)
    f=d-e
    r=t(max(c+1,1))//(t(b)*t(max(c+1-b,1)))
    if e==0:
        print((r-1)%1000000003)
    else:
        print((r-t(max(f+1,1))//(t(e)*t(max(f+1-e,1))))%1000000003)