0과 1의 쉼터

오늘은 피크민들에게 정수를 먹이고, 꽃잎을 2배로 얻을 수 있는 방법에 대해 소개하겠습니다. 피크민은 처음에 "잎사귀"로 시작합니다.저의 B-2입니다. 보시는 것처럼 머리 위에 "잎사귀"가 있습니다.피크민에게 "정수"를 주거나, 대열에 넣어 함께 산책하면 머리의 잎사귀는 "꽃봉오리"가 됩니다. 이렇게 머리위에 꽃봉오리를 핀 상태에서 정수를 주어 꽃잎을 피우면, 해당 꽃잎을 두배로 얻을 수 있습니다.  아침밥을 보고 눈 돌아간 노예입니다. 이후 피크민을 눌러 꽃잎을 채취 후 실제로 꽃잎 두개를 얻었는지 확인 해보겠습니다. 보시는 것처럼 하양 헬레보루스가 238개에서 정수 하나로 240개가 된 것을 확인할 수 있습니다. 이 방법은 피크민 머리 위에 "잎사귀"가 있을 때 일반 정수를 주거나 산책을 통해 꽃봉오..

문제https://www.acmicpc.net/problem/2482풀이바텀업보다 탑다운 방식으로 접근하면 쉬워지는 문제다. 원형을 이루는 N개의 색상환 표에 대해 인접하지 않은 색을 K개 선택하는 경우의 수를 구해야 한다.경우의 수가 너무 커지지 않게 1e9 + 3으로 나눈 나머지를 출력해야 한다. dp[N][K] : N개의 색상에 대해 인접하지 않는 K개의 색을 선택하는 경우의 수문제를 단순화해보자. 다음이 성립한다.dp[N][1] = Nif K > N / 2, dp[N][K] = 0문제에서 주어진 그림을 예시로 설명하겠다.우선 빨강색(N번째)을 선택해보자.N번째 색을 선택할 때, 인접한 N - 1번(다홍색)은 선택할 수 없다. N - 2번(주황)을 선택해야하고, 이 때 K - 1개의 색을 선택하면 ..