15990

🧷 문제 https://www.acmicpc.net/problem/15990 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 과정에서 같은 수를 두 번 이상 연속해서 사용하지 않는 방법의 수를 구하는 문제이다. 🛠 풀이 이 문제는 DP table을 1차원이 아닌 2차원으로 구성해야 해결할 수 있다. Step 1. 먼저 각 인덱스의 DP table을 길이 4의 리스트로 받는데 0번 인덱스에는 n을 만들 수 있는 방법의 수, 1 ~ 3번 인덱스에는 각 인덱스로 끝나는 방법의 수를 넣어준다. 예를 들면 d[3]의 경우 2 + 1, 1 + 2, 3 이렇게 총 3가지의 경우를 가지고 있고 1, 2, 3으로 끝나는 방법이 각 1개씩 존재하므로 d[3] = [3, 1, 1, 1]로 초기화해준다. 같은 ..