정수 n이 주어졌을 때, 이를 1,2,3의 합으로 나타내는 경우의 수를 알아내야하는 문제이다.
dp로 접근하여 간단하게 풀 수 있는 문제이다.
특히나, 11보다 작은 n만 주어진다고 하였으니, dp의 길이를 11 ( 0번 인덱스 ~ 10번 인덱스)로 잡으면 될 것이다.
먼저 n으로 1,2,3이 주어졌을 때의 경우의 수를 작성해놓고, dp를 위한 반복문을 시작한다.
dp는 항상 이전의 정보들을 사용한다.
그 과정에 겹치는 것이 없도록 자신만의 기준을 세우는 것이 중요하다.
먼저 dp[1]이니 (1)은 만들어져있을 것이다.
우리는 3을 더하여
(1) + 3 을 만들 수 있다.
(1) + 1 + 2 도 만들 수 있을 것이다.
하지만!! (1) + 1 + 2 는 (1) + 1 +2 로서, dp[2] 와 겹친다.
(1) + 1을 우리는 (2)로 볼 수 있기 때문이다.
따라서 우리는 dp[2], dp[3]에서 겹치는 경우가 생기지 않도록 (1) + 3 , 즉 dp[1]의 경우의 수 * 1 만큼의 경우의 수를 dp[4]로 더해준다.
따라서 dp[2]의 경우의 수 * 1 만큼 dp[4]에 더해준다.
따라서 dp[3]의 경우의 수 * 1만큼 dp[4]에 더해준다.
이를 점화식으로 정리하면 dp[4] = dp[3] + dp[2] + dp[1]이 된다.
이를 일반화하면, 4이상의 모든 자연수에 대하여, dp[i] = dp[i-1] + dp[i-2] + dp[i-3]을 만족한다.
이를 구현한 코드는 아래와 같다.
백준 7569: 토마토 (Swift) (0) | 2022.05.25 |
---|---|
백준 1697: 숨바꼭질 (Swift) (0) | 2022.05.25 |
백준 11657: 타임머신 (Swift) (0) | 2022.05.24 |
백준 15652: N과 M (4) (Swift) (0) | 2022.05.24 |
백준 15650: N과 M (2) (Swift) (0) | 2022.05.24 |