그랬었습니다

백준에서 단계별로 풀기를 위에서부터 100 문제 정도 풀면 동적 계획법이 나온다. 동적 계획법1 파트에서 4번까지는 피보나치 같은 비교적 간단한 문제만 나온다. 여기까지는 알고리즘에 대한 공부를 따로 하지 않아도 직관으로 어느 정도 풀 수준이라고 할 법하다고 생각한다. 하지만 이 문제는 대중적? 알고리즘의 한 부분인 Dynamic Programming을 공부하지 않으면 꽤나 고전할 법한 문제이다. 물론 따로 공부하지 않았다고 해서 풀지 못할 문제라는건 아니지만.. 여하튼 이 문제는 동적 계획법을 처음 공부한 사람이 익숙해지기 위해 풀어보는 입문용 문제라고 봐도 좋을 것 같다. 자 이제 문제를 살펴보자. i번째 집은 i-1번째와 i+1번째 집과 같은 색으로 칠할 수 없다. 1번째 집부터 차례대로 집의 색을..