목록2482 (1)

프로그래밍에 대한 고찰 및 생각

[알고리즘][4][백준_2482][Python3] - 색상환

문제이해 문제에서는 다채로운 색이 등장하지만 단순하게 n등분 되어있는 원에서 인접하지않게 k개를 색칠하는 경우의 수를 구하는 문제이다. 알고리즘 전략 알고리즘 구현을 위한 첫걸음은 노트북에서 잠시 손을 내려놓고 펜과 종이로 직접 구해보는것이다. 무언가 규칙성이 있을것같았고 점화식이 있을것같았다. N=6 K=2 일때의 경우로 생각해보자 6개의 칸이 있고 2칸을 이웃하지않게 색칠하는 경우의 수를 구하는 문제이다. 이를 편의상 앞으로 color(6,2) 라고 하자 color(6,2)를 구하기 전에 color(5,2) 를 한번보자 color(5,2)는 다음과 같이 5가지이다 여기서 마지막 칸을 두개로 쪼갠다면 다음과 같다. 바로 위의 5가지 경우는 color(6,2) 의 경우의 수들중 일부이다. color(6,..
알고리즘/백준 2020. 1. 15. 23:12
이전 Prev 1 Next 다음