문제 유형별 해결 Tip

다이나믹 프로그래밍 문제

* 다이나믹 문제만이 가지고 있는 패턴을 익히기 위해 많은 문제를 풀어보는 것이 중요함

 

1. 결과를 특정한 수로 나눈 나머지를 출력하라는 유형의 문제
- 접근 방법 : 최종 연산된 결과에만 나머지 연산을 수행하면 안되고, 값을 계산할 때 마다 d 배열에 나머지를 저장해야함.
                        그 이유는 출제자가 이미 중간 연산의 결과가 데이터의 저장범위를 넘어가는 것을 알고 있기에 이런 문제를 내는 것이고,
                        이렇게 해주지 않으면 의도된 답을 구할 수 없게 된다.

 

2. 2차원 이상의 배열을 사용해야하는 유형의 문제 

- 접근 방법 : 점화식을 만들고 구현하는 것은 1차원 배열을 사용하는 문제와 동일하니, 1차원 배열로 풀어야하는지
                        2차원 배열로 풀어야 하는지 판단하는 능력을 길러야 한다.

                        1차원 배열로 풀 수 있는 문제의 예로는 '이친수' 문제와 같이 한 자리에 0 또는 1만 올 수 있는 경우.
                        2차원 배열로 풀 수 있는 문제의 예로는 '쉬운 계단수' 문제와 같이 한 자리에 0~9까지의 수가 올 수 있는 경우.

 

3. 어떤 문제든 Bottom-up 방식의 구현이 훨씬 쉽다.

 

4. 배열 d에 2차원 배열을 사용하여 해결하는 경우도 있지만 일단 기본은 1차원 배열을 사용하는 것이다.