01 타일 - (Dynamic programming - 동적계획법) ★☆☆

 

이번 문제는 먼저 글로 점화식을 세워보았다.

간단히 An = An-1 + An-2 라는 점화식이 도출되었다.

 

처음에는 재귀함수로 코드를 짜서 제출을 하였는데, 런타임오류(재귀함수depth가 깊어서)가 발생하였고

이를 해결한 뒤에는 계속 메모리 초과가 되었다.

 

따라서 재귀함수를 포기하고 for문으로 간단히 코딩을 하니 문제해결이 되었다.

 

이 문제에서의 핵심은 15746으로 나눈 나머지 값을 구하는 건데, 마지막 출력시에 이를 해주면

메모리 초과가 발생하게 된다. dp배열에 들어가는 값이 크기 때문이다.

 

어차피 나중에 합한 값에서의 나머지를 구하나 나머지들의 합을 구하나 같기 때문에

 

dp에 15764로 나눈 나머지 값을을 저장한다.

 

이번 문제를 통해 얻을 수 있었던 점은

 

꼭 재귀함수만 생각할 것이 아니라 메모리와 시간의 초과에도 신경을 써야겠다는 것이다.