[백준 15990번] 1, 2, 3 더하기 5 (java)

백준 15990번 : 1, 2, 3 더하기 5

15990번: 1, 2, 3 더하기 5

 

정수 n을 1,2,3의 합으로 나타내되, 1,2,3 이 연속으로 더해져서는 안된다.

백준 9095번 : 1,2,3, 더하기 문제에서 약간 변형하여 다이나믹 프로그래밍으로 해결하였다.

기존에 9095번 문제에서 dp 점화식은 다음과 같았다.

dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 

 

그런데 이번 문제에서는 같은 수가 연속으로 나오면 안되므로 dp를 이차원 배열로 만들어서 dp[n] 를

연산의 마지막이 1로 끝나는지, 2로 끝나는지, 3으로 끝나는지에 따라 dp[n][1], dp[n][2], dp[n][3]으로 구분하였다.

 

예를 들어

dp[3]의 경우, 2 + 1 은 dp[3][1]에 포함되고, 1 + 2는 dp[3][2]에 포함되고, 3은 dp[3][3]에 포함된다.

dp[4]의 경우, 1 + 2 + 1, 3 + 1 는 1로 끝나니까 dp[4][1]에 포함되고 -> dp[4][1] = 2

                  1 + 3 는 3으로 끝나니까 dp[4][3]에 포함된다. -> dp[4][3] = 1 

 

dp를 이차원 배열로 만들어서 각 경우를 구분하였으므로 위의 점화식을 변형시키면 다음과 같이 된다.

dp[n][1] = dp[n-1][2] + dp[n-1][3]

dp[n][2] = dp[n-2][1] + dp[n-2][3]

dp[n][3] = dp[n-3][1] + dp[n-3][2]

 

정수 n이 되도록 하는 연산 중에서 1로 끝나는 경우는 그 전까지의 합이 n-1이 되어야 할 것이다.

또한, 마지막이 1로 끝나야 하므로 그 직전에는 1로 끝나면 안되기 때문에 dp[n-1][1]는 포함시키면 안된다.

(1로 끝나지 않으면서, 합이 n-1이 되는 경우) + 1

그러므로 dp[n][1] = dp[n-1][2] + dp[n-1][3]가 된다.

 

dp[n][2]와 dp[n][3]도 마찬가지이다.

정수 n이 되도록 하는 연산 중에서 2로 끝나는 경우는 그 전까지의 합이 n-2이 되어야 한다.

또한, 마지막이 2로 끝나므로 그 직전 연산은 2로 끝나면 안되기 때문에 dp[n-2][2]는 포함시키면 안된다.

(2로 끝나지 않으면서, 합이 n-2이 되는 경우) + 2

그러므로 dp[n][2] = dp[n-2][1] + dp[n-2][3]가 된다.

 

정수 n이 되도록 하는 연산 중에서 3으로 끝나는 경우는 그 전까지의 합이 n-3이 되어야 한다.

또한, 마지막이 3으로 끝나므로 그 직전 연산은 3으로 끝나면 안되기 때문에 dp[n-3][3]는 포함시키면 안된다.

(3으로 끝나지 않으면서, 합이 n-3이 되는 경우) + 3

그러므로 dp[n][3] = dp[n-3][1] + dp[n-3][2]가 된다.

 

소스코드 :