Notice
Recent Posts
Recent Comments
Link
목록` (1)
티끌모아 태산
백준 9095번: 1, 2, 3 더하기
이 문제는 다이나믹 프로그래밍을 이용하여 풀 수 있다. dp 1차원 배열을 생성하고, dp[n] 는 정수 n을 1,2,3 의 합으로 나타낼 수 있는 경우의 수를 의미한다. dp[1] 은 1로만 나타낼 수 있으므로 1가지이다. n = 1 일 때, 1 한 가지이므로 dp[1] = 1 이다. n = 2 일 때, 1 + 1 2 두 가지이므로 dp[2] = 2 이다. n = 3 일 때, 1 + 1 + 1 2 + 1 1 + 2 3 총 4가지이므로 dp[3] = 4 이다. n = 4 일 때, 1 + 1 + 1 +1 2 + 1 + 1 1 + 2 + 1 3 + 1 1 + 1 + 2 2 + 2 1 + 3 총 7가지이므로 dp[4] = 7 이다. 그런데 n = 4 인 경우의 수에서 아래의 빨간색 부분의 연산은 dp[3]에 ..
코딩/코딩테스트
2024. 4. 22. 16:25