#9465 (1) 썸네일형 리스트형 [Baekjoon]9465.스티커(DP) Baekjoon #9465. 스티커http://www.acmicpc.net/problem/9465 처음에 문제를 보고 완전탐색으로 풀 수 있겠다고 생각했지만 알고리즘 분류에 DP로 되어 있어서 DP로 풀기로 했다. 완전탐색으로 풀어보고 비교해봐야겠다. 일단 DP를 이용해서 풀자. 문제에서 모서리를 공유하며 인접한 스티커는 뗄 수 없다고 했다. DP로 풀기 위해 N번째 열의 상태와 N-1번째 열의 상태를 비교하며 어떤 관계가 있는지 알아야 한다. 이렇게 스티커를 열로 분해하는 아이디어가 중요한것 같다. 먼저 스티커는 2Xn 이고 N번째 열이 표와 같은 상태일때 N-1번째에 올 수 있는 상태는 다음과 같다.(같은 행에 OO가 올 수 없음.)점화식을 세우기 위해서 배열 d를 정의한다. d[N][k] : 스티커.. 이전 1 다음
