[백준][C#] 9095 1, 2, 3 더하기 - 실버3

문제보기

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

DP(다이나믹 프로그래밍)을 사용하는 문제이다.

 

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

점화식을 세우기 위해 규칙을 파악할 필요가 있다.

정수 1, 2, 3을 나타내는 방법을 파악해보자.

 

1: 1

2: 1+1, 2

3: 1+1+1, 1+2, 2+1, 3

 

따라서

dp[1] = 1;
dp[2] = 2;
dp[3] = 4;

라는 것을 알 수 있다.

여기서 재미있는 점을 발견할 수 있는데, dp[4]는 dp[1] + dp[2] + dp[3]을 합친 값인 7이라는 것이다.

 

dp[5]의 경우도 동일하다.

1. 1+1+1+1+1

2. 1+1+1+2

3. 1+1+2+1

4. 1+2+1+1

5. 2+1+1+1

6. 1+1+3

7. 1+3+1

8. 3+1+1

9. 1+2+2

10. 2+1+2

11. 2+2+1

12. 2+3

13. 3+2

dp[5] == dp[2]+dp[3]+dp[4] == 13

 

왜 이런 결과가 나올까?

dp[4]의 경우를 다시 한 번 살펴보자.

• 1+1+1+1 == 1+1+1     +1
• 1+1+2 == 1 + 1     + 2
• 1+2+1 == 1 + 2     + 1
• 2+1+1 == 2 + 1     + 1
• 2+2 == 2     + 2
• 1+3 == 1     + 3
• 3+1 == 3     + 1

이런식으로 해석할 수 있는데, 이를 더해지는 숫자에 따라 나누어보면?

• 1+1+1+1 == 1+1+1     +1
• 1+2+1 == 1 + 2     + 1
• 2+1+1 == 2 + 1     + 1
• 3+1 == 3     + 1

 

• 1+1+2 == 1 + 1     + 2
• 2+2 == 2     + 2

 

• 1+3 == 1     + 3

dp[3]의 원소들에 1을 더한 값,

dp[2]의 원소들에 2를 더한 값,

dp[1]의 원소에 3을 더한 값이다.

이렇게 이전 숫자들의 경우의 수에 대해 관계성을 알아낼 수 있었다.

 

따라서 아래와 같은 점화식을 도출해낼 수 있다.

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

 

 

코드 보기

 

	static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());
            
            int T = int.Parse(reader.ReadLine());

            int[] nums = new int[11];
            nums[1] = 1;
            nums[2] = 2;
            nums[3] = 4;

            for(int i = 0; i < T; i++)
            {
                int n = int.Parse(reader.ReadLine());
                if (nums[n] != 0)
                {
                    print.WriteLine(nums[n]);
                    continue;
                }

                for (int j = 1; j <= n; j++)
                {
                    if (nums[j] != 0)
                        continue;

                    nums[j] = nums[j - 1] + nums[j - 2] + nums[j - 3];
                }

                print.WriteLine(nums[n]);
            }
        }