문제 바로가기
문제:
색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다.
색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다. 주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자. 먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 있게 10개의 색을 선택하는 경우의 수는 2이지만, 시각적 대비 효과를 얻을 수 있게 11개 이상의 색을 선택할 수 없으므로 이 경우의 수는 0이다. 주어진 정수 N과 K에 대하여, N개의 색으로 구성되어 있는 색상환 (N색상환)에서 어떤 인접한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 프로그램을 작성하시오.
입력:
입력 파일의 첫째 줄에 색상환에 포함된 색의 개수를 나타내는 양의 정수 N(4 ≤ N ≤ 1,000)이 주어지고, 둘째 줄에 N색상환에서 선택할 색의 개수 K(1 ≤ K ≤ N)가 주어진다.
출력:
첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다.
풀이:
어렸을때 많이 보던 그림이네요
여기서 중요한건 인접한 두 색은 동시에 사용 못하는것과
원형이라는점
만약에 원형 시작점을 색칠하면 그 전껏도 색칠을 못하고 그 다음것도 색칠을 못합니다.
그렇지 않은경우에는
내기준 왼쪽꺼 선택 못하니깐 그 왼쪽꺼 i-2에서 j-1 개 선택한거 뽑아서 내꺼 까지 하다 칠해주고
아니면 왼쪽꺼 이미 선택된거를 가져와서 안칠한상태로 더해주면 된다 dp[i-1][j]
== >
dp[i][j] = dp[i-2][j-1] + dp[i-1][j]
근데 동그라미라면? n-1 도 못 고르고 1번째도 못 고른다.
그럼 i-3 개 중에 j-1개 와
i-1개에서 j개를 선택하는것을 더해주면된다.
dp[i][j] = dp[i-3][j-1] + dp[i-1][j]
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n = int(input())
k = int(input())
# [i개의색중][j개의 색 선택]
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(n + 1):
# 아무것도 안 뽑음
dp[i][0] = 1
# 1장만 뽑으면 됨 => n길이만큼
dp[i][1] = i
for i in range(2, n + 1):
for j in range(2, k + 1):
# i = n 이면 동그라미니까 좌 우 선택 못함
if i == n:
dp[i][j] = dp[i - 3][j - 1] + dp[i - 1][j]
# i번째 뽑으면 왼쪽꺼 못 뽑으니까
# i-2개 중에서 j-1 개
# ++++
# i-1개 중에서 j개
else:
dp[i][j] = dp[i - 2][j - 1] + dp[i - 1][j]
dp[i][j] %= 1000000003
print(dp[n][k])
댓글