안녕하세요 이번 포스팅은 바로
백준 알고리즘 1003번(자바)
문제입니다
문제
다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.
fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.
●fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
●fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
●두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
●fibonacci(0)은 0을 출력하고, 0을 리턴한다.
●fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
●첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
●fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.
1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.
출력
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
예제 입력
예제 출력
문제풀이
이 문제는 두 가지 방법으로 나눠서 풀 수 있습니다.
- 방법 1 : 호출 시 카운트(시간초과 문제 발생)
fibonacci(0)이 호출될 때 zero_cnt++ 해주고 fibonacci(1)이 호출될 때 one_cnt++를 해줍니다.
이렇게 하면 문제에서 원하는 것 처럼 fibonacci(0),fibonacci(1) 호출 수를 알 수 있고 이를 그대로 출력해주면 됩니다.
위의 코드처럼 카운트 해주시면 이클립스에서는 문제없이 돌아가지만 백준 사이트에서는 시간초과가 날 가능성이 높습니다.
왜냐하면 이 방식은 시간이 오래걸린다는 단점이 있습니다. 그 이유는 0,1의 호출 수를 알기 위해 피보나치 함수를 계속 이용해야 한다는 점인데
이렇게 된다면 N의 값이 커지면 커질수록 피보나치 함수의 호출 수는 훨씬 더 많아지고 이로 인해 시간을 많이 잡아먹을 수 밖에 없습니다.
이를 해결하기 위해서 다른 방법을 이용해야 합니다.
-방법 2 : 규칙 찾기( 1. Scanner(시간초과) 2. BufferedReader)
n을 0부터 시작해서 1씩 값을 올려 결과를 얻으면 아래처럼 일정한 규칙이 보이게 됩니다.
n(0) -> zero[0] = 1 , one[0] = 0
n(1) -> zero[1] = 0 , one[1] = 1
n(2) -> zero[2] = 1 , one[2]= 1
n(3) -> zero[3] = 1 , one[2] = 2
n(4) -> zero[4] = 2 , one[3] = 3
n(5) -> zero[5] = 3 , one[3] = 5
이러한 규칙들을 정리해보면
zero[n] = zero[n-1] + zero[n-2]
one[n] = one[n-1]+one[n-2]
위와 같은 규칙으로 정리할 수 있는데 이렇게 정리된 규칙을 이용한다면
시간이 많이 걸릴 fibonacci 함수를 계속 쓰지 않아도 원하는 값을 구할 수 있습니다.
이러한 규칙을 이용하기 위해
0,1의 호출 수를 저장하기 위한 배열 선언을 해줍니다.
그리고 나서 zero,one의 첫번째 두번째 인덱스 값을 넣어주는데 이렇게 먼저 집어 넣는 이유는 [n] = [n-1]+[n-2]이기 때문입니다.
정리해서 코드를 짜면 위와 같이 나옵니다.
이렇게 풀고 내면
시간초과가 나옵니다.
이유는 바로 Scanner 입니다.
Scanner를 사용하면 쉽게 풀 수 있지만 Scanner를 사용하면 시간이 많이 걸린다는 단점이 있습니다.
이를 해결하기 위해서 Scanner 대신 BufferedReader,Writer를 이용합니다.
이를 BufferedReader,Writer로 해결하면 위에 보이는 코드처럼 정리할 수 있습니다.
느낀점
이때까지 scanner만 사용했는데 scanner가 시간이 많이 잡아먹는 지는 몰랐다.
scanner 대신 bufferedreader,writer로 시간이 얼마 걸리지 않을 수 있다는 것도 알 수 있었고
reader,writer를 사용하는 방법도 알 수 있었다.