백준 15993 자바 - 1, 2, 3 더하기 8 (BOJ 15993 JAVA)

f(n)을 정수 n을 1,2,3의 덧셈으로 표현 가능한 가지수라 정의하면,

f(n) = f(n-1) + f(n-2) + f(n-3) 이다.

왜냐하면 예를들어 n=5라면, f(5)는 f(4)의 모든 표현의 뒤에 +1을 붙인 것 + f(3)의 모든 표현의 뒤에 +2를 붙인 것 +

f(2)의 모든 표현의 뒤에 +3을 붙인 것 이기 때문이다.

위 식을 배열로 나타내자면 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]; 이 된다.

그런데 이상태로는 짝수가지수와 홀수가지수를 알 수 없다. 따라서 dp를 2차원 배열로 확장해서 dp[a][b]로 보자.

a가 1,2,3의 합으로 나타내려는 정수, b는 0일 때 짝수인 경우, 1일 때 홀수인 경우를 나타낸다고 하자.

그럼 dp[n][0]은 정수 n을 표현하는 가지수 중 짝수개를 더한 경우, dp[n][1]은 홀수개를 더한 경우 이다.

홀수개를 더한 것에서 하나를 더 더하면 짝수개가 되므로, 즉

dp[n][0] = dp[n-1][1] + dp[n-2][1] + dp[n-3][1] 이다.

마찬가지로

dp[n][1] = dp[n-1][0] + dp[n-2][0] + dp[n-3][0] 도 성립한다.

이제 1,000,000,009로 나눈 나머지를 출력해야 한다는 부분이 남았는데,

(A+B+C) % MOD = (A%MOD + B%MOD + C%MOD) % MOD와 동일하다. (나머지 연산의 분배법칙에 따라)

그러니 그냥 매번 계산할 때 마다 1,000,000,009로 나눠주면 된다.

그럼 최대 2 x 1,000,000,009 내에서 모든 연산이 진행되므로 int 타입 범위를 넘는 경우 없이 정상적으로 연산 가능하다.

만약 전부 계산 후 마지막에 나눠주려면 파이썬은 그냥 그렇게 하면 되고, 자바라면 BigInteger를 써야 하는데, 상당히 느려서 시간 내에 통과될지는 잘 모르겠다.

댓글