[Go] 백준 1003번 (피보나치)

문제

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

---

문제 풀이

문제 해석 및 계획

우선 재귀함수를 통하여 피보나치를 먼저 구현하였습니다.

구현 후 0일 때 return이 아닌 check0이란 변수를 1 증가시키고 1일 때 return이 아닌 check1이란 변수를 1 증가시키도록 변형하면 값을 얻을 수 있겠다고 생각하였습니다.

오답 노트

package main

import (
	"bufio"
	"fmt"
	"os"
)

var rx = bufio.NewReader(os.Stdin)
var wx = bufio.NewWriter(os.Stdout)
var check0, check1 int

func main() {

	defer wx.Flush()

	var testNum int

	fmt.Fscanln(rx, &testNum)

	for i:=0 ; i<testNum ; i++{
		var num int
		fmt.Fscanln(rx,&num)
		fibonachi(num)
		fmt.Fprintln(wx, check0, check1)
		check0, check1 = 0, 0
	}
}

func fibonachi(n int){
	if n == 0 {
		check0++

	} else if n == 1 {
		check1++
	}else {
		fibonachi(n-1)
		fibonachi(n-2)
	}
}

이전에 배운 bufio를 통하여 입출력을 하여 시간을 절약할 것이라고 생각하였지만

결과는 같이 나오는 것을 확인하였지만 재귀함수의 시간문제로 인하여 시간초과를 받았습니다.

정답

package main

import (
	"bufio"
	"fmt"
	"os"
)

var rx = bufio.NewReader(os.Stdin)
var wx = bufio.NewWriter(os.Stdout)

func main() {

	defer wx.Flush()

	var testNum int

	fmt.Fscanln(rx, &testNum)

	for i:=0 ; i<testNum ; i++{
		var num int
		fmt.Fscanln(rx,&num)
		check0, check1 := fibonachi(num)
		fmt.Fprintln(wx, check0, check1)
	}
}

func fibonachi(n int) (check0, check1 int) {
	if n == 0 {
		return 1, 0
	}else if n == 1 {
		return 0, 1
	}else {
		var previous, now int = 1, 1
		for i:=0;i<n-2;i++{
			previous, now = now, previous + now
		}
		return previous, now
	}
}

피보나치를 반복문으로 수정하고 어떻게 0의 개수와 1의 개수를 확인할까 고민하던 중

피보나치는 n-1과 n-2 번째 수의 합이기에 재귀적으로 호출하였던 것에서 힌트를 얻었습니다.

n은 n-1번째가 출력한 0과 1의 수 + n-2번째가 출력한 0과 1의 수만큼 0과 1을 출력할 것이라고 생각하였습니다.

0과 1이 출력되는 횟수도 역시 각각 피보나치 값을 가지는 것을 확인하였고 0은 previous값, 1은 now값을 가진다는 것을 확인하여 함수의 출력을 previous와 now로 설정하여 출력하였습니다.

---

느낀 점

새로운 언어를 배울 때마다 마주하게 되는 피보나치이지만 문제를 조금만 변형하여도 로직을 새로 고민하게 되어 로직을 고민하는데 좋은 문제라고 느꼈습니다.

핵심은 0과 1의 출력 횟수가 피보나치 함수의 출력과 비슷하다는 것을 알기 위하여 피보나치의 특징을 알고 있어야 풀 수 있다는 점이라고 생각됩니다.