알고리즘/백준
1,2,3 더하기 5 15990번 백준
글을 쓰는 개발자
2020. 12. 2. 20:27
반응형
문제:www.acmicpc.net/problem/15990
15990번: 1, 2, 3 더하기 5
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
www.acmicpc.net
처음에 이 문제를 접 했을 때 기존 더하기 문제와 같이 피보나치의 꼴처럼 이전의 값을 단순히 더해나가면 될 줄 알았다. 그래서 문제의 푸는 방향을 오로지 총 갯수의 상관관계만 봤는데 그렇게 접근하면 안됐다. 이 문제는 사실 RGB거리 문제와 유사한 문제라 볼 수 있다. 방향성을 한 번 잘 못 잡으니깐 다른 방법이 생각이 나질 않았다. ㅠㅠ
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
MAX = 100000
mod = 1000000009
DP = [[0]*(3+1) for _ in range(MAX+1)]
DP[0] = [0, 0, 0, 0]
DP[1] = [0, 1, 0, 0]
DP[2] = [0, 0, 1, 0]
DP[3] = [0, 1, 1, 1]
for i in range(4, MAX + 1):
DP[i][1] = (DP[i - 1][2] + DP[i - 1][3]) % mod
DP[i][2] = (DP[i - 2][1] + DP[i - 2][3]) % mod
DP[i][3] = (DP[i - 3][1] + DP[i - 3][2]) % mod
for _ in range(int(input())):
N = int(input())
print(sum(DP[N])% mod)
#참고 https://br-brg.tistory.com/9
|
cs |
코드참고:br-brg.tistory.com/9
[Python]15990. 1,2,3 더하기 5
https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1차원의 DP로..
br-brg.tistory.com
위의 풀이법은 이렇다.
처음이 1이 있다면 다음에 올 숫자는 2 아니면 3이다. 그러므로 이전 단계의 DP[i-1]에서 2와 3의 값을 더하고, 처음이 2라면 1또는 3이므로 DP[i-2]에서 1과 3의 값을 더해나가는 식이다.
그렇게 하면 다음 와래와 같은 관계를 도출 해낼 수 있다.
|
1
2
3
4
5
|
for i in range(4, MAX + 1):
DP[i][1] = (DP[i - 1][2] + DP[i - 1][3]) % mod
DP[i][2] = (DP[i - 2][1] + DP[i - 2][3]) % mod
DP[i][3] = (DP[i - 3][1] + DP[i - 3][2]) % mod
|
cs |
반응형