[BaekJoon/백준] 1003번 | 복습 1회 완료

나를 상당히 짜증나게 했던 문제..

내가 1003번에 애정을 준 정도다.

문제 이름은 피보나치. 수학을 정말 암흑적으로 못하기 때문에, 제목부터 걱정이 많이 되긴 했다.

어디서 들어보긴 했는데..하며 문제를 읽었는데 정말 무슨 소린지 하나도 모르겠더라.

문제 이해하는데만 시간이 좀 걸렸, 아니 솔직히 문제를 풀면서도 이해를 못했던 것 같다.

 

머리가 나빠서, 항상 코딩할 때 충분한 구상이 없으면 안됐던 탓에 일단은 피보나치가 무슨 규칙을 갖고 있는지 눈으로 확인해야 했다.

 

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]);
        }
    }
}

결과는 통과

뭐지 이 간단하고 야매같은 찝찝함은?

 

 

---

2021.02.22 복습

다시 풀어봤음. 이제보니, 동적계획법을 알기도 전에 나는 동적계획법을 사용했었다.. 진짜 똑똑하다 나..!!

#include <stdio.h>

int N;
int input;
int arr[41];

int main() {
    
    scanf("%d", &N);
    
    arr[0] = 0; arr[1] = 1;
    
    for(int i = 2; i < 41; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    
    for(int i = 0; i < N; i++) {
        scanf("%d", &input);
        
        printf("%d %d\n", (input == 0)?1:arr[input - 1] ,arr[input]); // input이 0인 경우는 예외처리!
    }
    
}
/*
 
 0 1 1 2 3 5 8 13
 
 fibo(0) = 0  / 1 0
 fibo(1) = 1  / 0 1
 fibo(2) = 1  / 1 1
 fibo(3) = 2  / 1 2
 fibo(4) = 3  / 2 3
 fibo(5) = 5  / 3 5
 fibo(6) = 8  / 5 8
 fibo(7) = 13 / 8 13
 
 */