백준 오답노트/DP

백준 - DP 2449번 전구 / 문제풀이, 오답노트

= 접근 과정 ( 틀림 ) = 이렇게 N개의 전구와, K가지의 색 => 최대 200개의 전구, 최대 20개의 색이므로 완전 탐색을 이용하면 시간 초과로 분명히 오답! => O(N!), 이유는 N개의 색이 모두 다 다를 수 있기 때문 이러한 문제는 DP를 이용해서 시간을 줄이는게 핵심이다. 처음 나는 재귀 함수를 이용해서, 이미 거친 전구들은 return하는 형식으로 문제를 접근했다. 1. int[] arr = new int[n] 배열에 1, 1, 2, 3, 3, 3, 2, 2, 1, 1의 값을 넣고 0번 index의 값을 2로 바꿨을 때, 인접한 값(1번 index)이 0번째 값(1)이랑 같을 때 같이 2로 변경해주고 아니면 return을 하는 형식으로 count를 했다. 2. 모든 값이 k로 다 통일 ..