[C++] 백준 2193번 이친수

DP 문제

이런 류의 DP 문제는 항상 1부터 차례대로 해 보면서 점화식을 세우는 것이 중요하다.

 

시도 방식 & 문제 풀이

 

코드 전문

점화식을 구해서 코드로 구현했다.

규칙성이 바로 보이므로 점화식을 찾는데는 문제가 없었다.

근데 여기서 N이 90이 되면 엄청나게 큰 수가 된다.

따라서 dp배열을 int가 아닌, long long형태의 배열로 만들어 주는 것이 중요하다.

 

 

처음 시도는 TOP DOWN방식의 재귀형태로 시도했는데, 시간초과가 났다.

그리고 위 방식대로 풀었는데, OVERFLOW가 나서 틀렸습니다 가 나왔다.

자료형을 바꾸고 나서는 바로 맞출 수 있었다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.