BOJ G3 2482 색상환 JAVA
2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 읽기 아 역시 DP 문제는 쉽지 않다. 사실 그렇게 어려운 문제인 것 같지는 않지만.. 처음에 DFS로 했다가 2^1000이니까 당연히 시간초과가 나고, 거의 바로 아 DP인 것 같다는 생각을 했다. 그런데 처음에 N, K로 접근하지 않고, 첫 번째 원소를 선택하는 경우, 첫 번째 원소를 선택하지 않는 두 가지 경우를 생각했다. 즉, N, 2로 접근했다. 그런데 이렇게 하니 DP 배열에 경우의 수를 저장하는 게 아닌, 선택한 원소의 개수를 저장하게 되고 답을 제대로 구하지 못했다..
2024. 3. 12.
