본문 바로가기
반응형

Dynamic Programming3

[Leetcode] 1931. Painting a Grid With Three Different Colors 문제 설명m x n 크기의 격자가 있다.각 칸은 반드시 빨강(R), 초록(G), 파랑(B) 중 하나의 색으로 칠해야 한다.단, 서로 인접한 칸은 같은 색으로 칠할 수 없다.여기서 인접하다는 것은 상하좌우 방향을 의미한다.이 조건을 만족하도록 모든 셀을 칠하는 방법의 수를 구하라.답이 매우 클 수 있으므로 1,000,000,007 (10⁹+7) 로 나눈 나머지를 반환하라. 예시예제 1입력: m = 1, n = 1출력: 3설명: R, G, B 중 하나를 선택할 수 있다 → 3가지예제 2입력: m = 1, n = 2출력: 6설명: 첫 칸을 3가지 중 하나로 칠하고, 다음 칸은 나머지 2가지 중 하나 선택 → 3×2 = 6예제 3입력: m = 5, n = 5출력: 580986설명: 조건을 만족하는 방법 수는 매.. 2025. 5. 20.
[Leetcode] 2901. Longest Unequal Adjacent Groups Subsequence II 역시 Computational Thinking 정수는 Dynamic Programming 문제 유형이다.많이 풀어보고 익숙해지지 않으면 발상하기 쉽지 않은 사고 방식이라 더욱 매력적이다.오랜만에 재밌는 문제였다. 이런 유형 문제를 많이 풀어보고 싶다는 생각까지 들었다.물론 퇴근하고 여기에 갖다 바친 내 3시간은 전혀 재밌지 않다.사실 설명 자체가 DP 유형 문제 만들기 위해 어거지로 써놓은 느낌도 있고. 문제 설명문자열 배열 words와 정수 배열 groups가 주어진다.두 배열의 길이는 동일하며 각각의 인덱스 i는 하나의 단어와 해당 단어의 그룹을 나타낸다.우리는 [0, 1, ..., n-1]의 인덱스 중 일부를 골라 최장 부분수열(subsequence)을 선택해야 한다.단, 다음 조건을 만족해야 .. 2025. 5. 17.
[Leetcode] 790. Domino and Tromino Tiling 어려웠다.이 문제 때문에 연속으로 문제 푼 횟수에 해당하는 streak 기록도 깨졌다. 이 문제는 위 두 도미노를 배치하여 서로 다른 2 x n 모양을 만들 수 있는 경우의 수를 구하는 문제이다.n 값이 int 범위를 넘어갈 수도 있기에 $10^{9} + 7$ 으로 나눈 나머지 값을 반환한다. 배치하라, 경우의 수를 구하라.점화식 느낌이 오면서, Dynamic Programming 냄새가 물씬 풍긴다.그치만 냄새만 맡아서 뭐하는가.결국 풀 수 있어야 하는데, 모든 경우를 놓치지 않고, 중복 없이 셀 수 있는 점화식을 만들기가 쉽지 않았다. 예제 n = 4 일 떄, 11n = 5 일 때, 24n = 30 일 때, 312342182 이다. 풀이2개 도미노를 배치해서 나올 수 있는 끝 모양은 아래와 같이 .. 2025. 5. 6.
반응형

티스토리툴바