스티커
-
[백준] 9465번 스티커 (by Python)Programming/Algorithm 2021. 2. 14. 23:16
문제 제법 Dynamic Programming에 익숙해졌다고 생각했는데 점화식을 떠올리기가 힘들었던 문제. 메모이제이션 방법을 떠올렸지만 점화식의 형태를 구상하기가 힘들었다. 수열로 따졌을 때 새로 추가되는 column의 값들에 따라서 최댓값도 달라지기 때문에 그랬던 것 같다. 이 문제의 breakthrough는 크게 다음 2가지였던 것 같다. ① 새로운 값이 어떤 값이냐에 따라서 답이 달라진다면 다 대입해볼 것! ② 메모이제이션으로 해당 값까지의 최적 경로에 대한 축적을 한다는 것을 기억하고 무엇을 축적해야할지 생각할 것! 풀이 t = int(input()) for _ in range(t): n = int(input()) arr = [] ans = [[0] * n for _ in range(2)] fo..