백준 9095: 1, 2, 3 더하기 (Swift)

정수 n이 주어졌을 때, 이를 1,2,3의 합으로 나타내는 경우의 수를 알아내야하는 문제이다.

 

dp로 접근하여 간단하게 풀 수 있는 문제이다.

특히나, 11보다 작은 n만 주어진다고 하였으니, dp의 길이를 11 ( 0번 인덱스 ~ 10번 인덱스)로 잡으면 될 것이다.

 

먼저 n으로 1,2,3이 주어졌을 때의 경우의 수를 작성해놓고, dp를 위한 반복문을 시작한다.

 

dp는 항상 이전의 정보들을 사용한다.

그 과정에 겹치는 것이 없도록 자신만의 기준을 세우는 것이 중요하다.

 

dp[4]는 어떻게 구할까?

 

#dp[1]의 경우에서 출발해보자.  (n)이라는 것은 n길이를 만들 수 있는 모든 경우의 수, 어떤 경우든 상관 없이 모두 적용된다는 뜻이다.

먼저 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]에서는 (2) + 2만이 dp[3]과 겹치지 않고 4로 직진할 수 있다.

따라서 dp[2]의 경우의 수 * 1 만큼 dp[4]에 더해준다.

 

# 마지막으로 dp[3]에서는 (3) + 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]을 만족한다.

 

이를 구현한 코드는 아래와 같다.