1.
n ≤ m 인 경우, 마지막 계단은 무조건 밟고 중간 계단 n-1개는 밟거나 안밟거나 두 가지 경우가 있으므로 2^(n-1) 가지입니다. 이 부분을 재귀함수 말고 반복문으로 만들면 훨씬 빨라집니다. 이정도만 해도 Accept 될거예요
2.
아주 빠르게 만들고 싶다면 이차원 배열 answer[20][20]를 만들어서 answer[n][m]에 PoorWelsh(n, m) 결과를 저장해두고 사용해보세요. 이건 알고리즘 강의에서 배우게 될 내용이라 아직은 못해도 괜찮습니다.
비효율적인 이유는 예를들어 PoorWelsh(5,3)를 실행하면
1. PoorWelsh(5, 3) 실행
2. 1에서 PoorWelsh(4, 3) 실행
3. 1에서 PoorWelsh(3, 3) 실행
4. 1에서 PoorWelsh(2, 3) 실행
5. 2에서 PoorWelsh(3, 3) 실행 (3과 똑같은 계산을 한번 더 합니다.)
6. 2에서 PoorWelsh(2, 3) 실행 (4와 똑같은 계산을 한번 더 합니다.)
7. 2에서 PoorWelsh(1, 3) 실행
...
결론적으로 n, m이 커질수록 함수실행 횟수가 아주 커져서 느려집니다.
PoorWelsh 맨 처음에 printf("%d %d\n",n,m); 을 넣어보면 함수가 몇 번 실행되는지, 같은 함수가 얼마나 중복실행되는지 확인해 보실 수 있을거예요
