목록백준 #dp #9465 (1)

머신러닝 개발자의 러닝머신

[백준 9465] 스티커(Python)

문제 유형 dp 아이디어 이 문제를 읽고 처음에는 완전탐색을 떠올렸다. 하지만 dfs/bfs를 이용하면 선택하지 않은(이웃하지 않은) 스티커를 매 column마다 반드시 하나는 선택하기 때문에 한 column에서 스티커가 하나도 선택되지 않는 경우는 고려할 수 없을 것이라는 생각에 다른 아이디어를 생각했다. -> dp 아이디어 ! dp 테이블을 이용해 해당 칸까지 얻을 수 있는 점수를 매 칸마다 계산한다면 위의 한계점을 극복할 수 있을 것이라 생각했다. 해당 칸의 스티커가 선택된 경우, 이웃 column의 스티커가 선택될 수 있거나 선택되지 않을 수 있다는 점을 주의하자! 이웃 column의 스티커가 선택되지 않은 경우, 그 이전 column의 0 또는 1행의 스티커가 선택되는 경우가 존재한다 dp[i]..
알고리즘/boj 2023. 1. 25. 23:30
이전 Prev 1 Next 다음