24821 [BOJ] 2482번: 색상환 2482번: 색상환 풀이 원으로 계산하면 골치가 아파서 선형으로 만들어서 계산하고 나중에 원으로 만들어서 계산하면 된다. 조건 범위 내 모든 n에서 k=0일 땐 1이고(아무 것도 고르지 않는 것도 경우로 취급), k=1일 땐 n이다. n>1의 경우, n번째 색을 고르거나 안 고르는 두 가지 경우로 생각할 수 있는데 n번째 색을 고르면 n - 2개 중 k - 1개를 고른 것과 같고, n번째 색을 고르지 않으면 n - 1개 중 k를 고른 것과 같다. 다시 원으로 합칠 때는 양쪽 끝을 합친다고 생각하면 되기 때문에 선형의 양쪽 끝이 같은 경우를 생각해 줘야 한다. 양 끝에 색이 칠해져 있다면 이 경우는 불가능하므로 그걸 피하기 위해 양쪽 끝 중 하나를 잡아서 계산한다. 아까와 동일하게 n번째 색을 고르거나 안.. 2018. 5. 21. 이전 1 다음