백준 9461 : 파도반 수열

https://www.acmicpc.net/problem/9461

문제

1 2

풀이

  • 이 문제는 9095번과 매우 유사하다.
    9095번 포스팅

  • 9095번 같은 경우는 숫자 제한이 10개라 크기가 10인 배열을 미리 정의하여 그 배열에 수열을 입력해두고 출력하는 방법을 사용했었다.
  • 하지만 이 문제는 숫자 제한이 100개라 찻 번째 부터 100번째 수열까지 다 저장하기 보다는 그때그때 함수를 호출하여 풀어보자!는 생각으로 접근했다.

풀이1

  • 1, 2, 3번째는 다 1이므로 따로 조건문을 활용하여 빼주고 점화식인 p(n) = p(n-2) + p(n-3)을 함수로 빼주었다.
  • 🚨 하지만 오히려 시간초과 에러가 발생했다. 🤯

풀이2

  • 그래서 9095번에서 쓴 방법대로 크기가 101인 배열을 선언했다..
    • 101인 이유는 인덱스 번호와 수열 번호를 맞추기 위해서이다.
  • 👍 그랬더니 시간초과 에러 없이 잘 해결되었다.
  • 곰곰이 생각하다 처음부터 모든 것을 다 계산하고 추출하는 방식이 그때그때 함수를 호출하여 계산하는 것보다 시간이 덜 걸린다는 것을 깨달았다. 😅 당연히 호출 횟수가 많아지면 시간도 늘어나는 건데 왜 풀이1이 더 빠르다고 착각했을까..!? 바보짓을 했구만..💦

완성된 코드

댓글남기기

참고