[BOJ 15990] 1, 2, 3 더하기 5
1,2,3으로 만들 수 있는 숫자의 조합 이전의 값을 참조하기 때문에 DP를 사용하여 문제를 풀었다. 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다. 1+2+1 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 조건 연속으로 오는 숫자는 불가능 (ex : 1+1+1) 1개 이상의 숫자를 사용 1,000,000,009로 나눈 나머지를 출력 끝나는 숫자가 1인경우, 2인경우, 3인경우를 카운트하여 미리 저장하여 놓는다. 1 == x 2 == y 3 == z dp[N] = x, y, z dp[1] = 1, 0, 0..
더보기