나를 상당히 짜증나게 했던 문제..
문제 이름은 피보나치. 수학을 정말 암흑적으로 못하기 때문에, 제목부터 걱정이 많이 되긴 했다.
어디서 들어보긴 했는데..하며 문제를 읽었는데 정말 무슨 소린지 하나도 모르겠더라.
문제 이해하는데만 시간이 좀 걸렸, 아니 솔직히 문제를 풀면서도 이해를 못했던 것 같다.
머리가 나빠서, 항상 코딩할 때 충분한 구상이 없으면 안됐던 탓에 일단은 피보나치가 무슨 규칙을 갖고 있는지 눈으로 확인해야 했다.
N : 인덱스 번호 / P : 피보나치 수열 / 0 : 0의 갯수 / 1 : 1의 갯수
// N 0 1 2 3 4 5 6 7 8
// P 0 1 1 2 3 5 8 13 21
// 0 1 0 1 1 2 3 5 8 13
// 1 0 1 1 2 3 5 8 13 21
문제에서 원하는 결과값이 0의 갯수와 1의 갯수라서, 대충 정리하고 나니까 눈에 보이기 시작했다.
결과는, 피보나치 함수에 N을 넣은 값 = 1의 갯수, 피보나치 함수에 N-1을 넣은 값 = 0의 갯수 라는 규칙을 찾아낼 수 있었다.
그래서 그냥 피보나치 함수 구현해서, IntelliJ에 실행해보니 결과도 잘 나오길래 바로 제출 넣었는데
"시간초과" 뜨길래 당황했다. 그래서 진짜 이런저런 많은 방법으로 메모리와 코드를 줄이려고 발악을 했는데도.. "시간초과"
정말 뭐 어쩌라는건가 싶었다.
그러다, 재귀함수가 정말 메모리와 시간을 많이 잡아먹는 것 같긴 한데..이 부분을 바꿔볼 순 없을까 생각했다.
여태까지 뭣모르고 해맑게 피보나치 함수를 재귀함수로 이용해서 결과를 도입했는데 아마 이게 문제가 됐던건가 싶어서, 아예 테스트 케이스 집어넣기 전에 배열로 피보나치 값들을 다 만들어놨다가 써주자는 생각을 했다.
물론 N값을 받을때마다 그 크기만큼의 배열을 만들어서 해 줄 수도 있지만.. 테스트 케이스 당 불필요한 시간이 늘어날 것 같았다.
문제에서 주어진 N이 0 또는 40이하의 자연수라길래, 그냥 배열 이만큼 만들어서 피보나치 값들 지정해줬다. 물론 일일히 숫자 하나하나 넣은게 아니라 0, 1인덱스에만 넣어주고 for문으로 돌렸다. 그리고 N값 받을 때 마다 배열에서 꺼내 쓰니 "개꿀인데, 이게 맞나..?" 싶었다.
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
int[] arr = new int[41];
arr[0] = 0; arr[1] = 1;
for(int z = 0; z < 39 ; z++) // z+2는 41이므로 z<39
{
arr[z+2]=arr[z]+arr[z+1];
}
int T=0;
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int i = 0; i < T ; i++)
{
int N = scanner.nextInt();
if(N==0)
System.out.println("1 0");
else
System.out.println(arr[N-1]+" "+arr[N]);
}
}
}
결과는 통과
뭐지 이 간단하고 야매같은 찝찝함은?
