Skip to main content

1931 - Painting a Grid With Three Different Colors

info

풀이 키워드​

스포주의

DP


풀이 코드​

info
  • 메모리: 0 KB
  • 시간: 0 ms


풀이 해설​

단순 백트래킹은 TLE 터지는데 DP로 접근하자니 메모이제이션 적용하기 빡센 유형이다.

왜냐하면 메모이제이션을 위해 DP state를 '적당하게' 정의해야 하는데

현재 칸, 또는 인접 칸(위쪽, 왼쪽)의 칠해진 색을 state 정의로 사용하면 WA이기 때문이다.

WA1

memo[i][c] -> ❌​


WA2

memo[i][tc][lc] -> ❌​


메모​

  • 카카오 공채 고난이도 정도면 나올수도
  • 이 문제도 matrix exponentiation으로 접근 가능하다.
    • 하지만 실전적으로는 classic DP 방식이 우선시된다.