[백준 9095] [JAVA] 1, 2, 3 더하기
9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이 dp[i] = i를 정수 1, 2, 3의 합으로 표현할 수 있는 방법의 수 초기값은 dp[1] = 1 dp[2] = 2 dp[3] = 4 이다. 4는 (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (1+3), (3+1), (2+2)로 표현이 가능하다. 여기서 (1+3), (3+1), (2+2) 해당 부분을 눈여겨 보자 3을 정수 1, 2, 3의 합으로 나타내는 방법의 수는 dp[3], 2는 dp[2], 1은 dp[1]이다. 이렇게 문제를 작게 쪼개는게 가능해진다. 이를 사용해서 점화식을 세워보면 dp[i] = dp[i-1] + ..
2023. 8. 29.