[필수 알고리즘] DP

개념

- Dynamic Programming

- 이전의 값을 재활용하는 알고리즘

- 예시 : 1~10 숫자중, 이전 값들을 합한 값을 구하라

- 이전의 값을 활용해서 시간복잡도를 줄일 수 있음

- 점화식이 있어야 풀기 쉬움(An = An-1 + An-2)

* for문을 이용해 값을 도출할 때 이전의 결과값과 현재 값을 더하면 시간복잡도를 줄일 수 있음 

O(N^2)에서 O(N)이 될 수 있음

 

아아디어

- A1 : 1, A2 : 2, A3 : 1 + 2

- An = An-1 + An-2

-for문으로 3부터 N까지 돌면서

- 이전값과, 그 이전값을 더해서 저장(이때 10007로 나눈 나머지 값)

 

시간복잡도

- for : N > O(N)

 

자료구조

- 방법의 수 배열(An) : int[]

 

문제풀이

- 백준 11726

 

1. 

/*
1. 아이디어
- 점화식 : An = An-1 + An-2
- N값을 구하기 위해 for문으로 3부터 N까지 값을 구해주기
- 이전값, 그 그이전값을 더해, 10007로 나눠 저장

2. 시간복잡도
- O(N)

3. 자료구조
- DP값 저장용(경우의 수) : int[]
*/


class num_11726
{
    static void Main(string[] args)
    {
        var sr = new StreamReader(Console.OpenStandardInput());
        var sw = new StreamWriter(Console.OpenStandardOutput());

        int n = Convert.ToInt32(sr.ReadLine());

        List<int> result = new List<int>() { 0, 1, 2 };
        for (int i = 3; i < n + 1; i++)
        {
            result.Add((result[i - 1] + result[i - 2]) % 10007);
        }

        sw.WriteLine(result[n]);
        sw.Flush();
        sw.Close();
        sr.Close();
    }
}

 

- 11726의 문제를 이용해 규칙을 보면 n이 1이면 1, n이 2면 2, n이 3이면 3이라는 값이 나온다

- 이러한 규칙을 기반으로 먼저 list에 0,1,2 라는 규칙을 담은후 An = An - 1 + An - 2의 식에 출력값을 10007로 나눈 나머지 값을 출력한다고 했으니 최종 식은 "(result[i - 1] + result[i - 2]) % 10007"가 되고 이것을 담고 result[n]값을 출력

 

 

참고영상

- 바로가기