[Java] 백준 1003번 [피보나치 함수] 자바

: ) YOUNG·2022년 4월 8일

DP Java algorithm 백준

알고리즘

목록 보기

87/417

백준 1003번
https://www.acmicpc.net/problem/1003

문제

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

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

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

출력

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

예제 입력 1

예제 출력 1

2
6
22

생각하기

이 문제는 동적계획법의 개념을 익힐 수 있는 문제이다

물론... 나는 이 문제가 처음에 동적계획법인지 모르고.. 그냥 문제를 풀었음
당연히 문제를 풀수 있다면 정답은 나오긴한다.

근데 시간초과가 나옴 그래서 뭐가 문제일까 찾아보다가..
요점이 제한시간이라는 걸 알게됬다

이 문제의 포인트는 0.25초 만에 정답을 출력할 수 있는 기술을 요구하는 문제였다.
내 입장에서는 아무리 고민을 해도 풀 수 없는 문제여서 다른 분들의 코드를 참고하기로 했다.

피보나치 함수 문제 풀이

결국 풀이를 보고 나서 알았지만, 동적계획법(DP)를 사용해서 풀어야 하는 문제였다.

동작

2번째 반복을 통한 동적계획법은 풀면서 어떻게 회전하며, 동작하는지 이해는 했지만,
설명을 내가 하기보단 위에서 하신 분의 설명을 보는게 더 잘 이해가 될거라고 생각해서 pass하겠다.

첫 번째 배열을 통한 동적계획법이 가장 많이 쓰이는 방법이라고 한다.

반복되면 같은 값이 나올 때 지속적으로 나오는 값은 배열에 저장을 해두면
다음에 그 값이 나올 때 계산을 하지 않고 건너 뛸 수 있기 때문에 속도가 훨씬 빨라지는 것이다.

반복문을 통한 DP에서 dp 배열을 int형이 아닌 Integer형으로 만드는 이유는 null값을 통해 비교하려고 하기 때문이다.

int형으로 배열을 만들게 되면 0값으로 모두 초기화가 되어 생성되는 반면 Integer형 배열은 객체형으로 null값으로 초기화 되어 생성되기 때문에 null값 비교가 가능하다

만약 int형 배열로 만들고 싶을 경우, 0 이하의 숫자로 따로 반복문을 통한 초기화를 진행해준다면, 똑같이 만들수 있지만 굳이 그렇게 하는것 보다는 Integer 배열을 사용하는 것이 더 효율적이다.

동적계획법 맛보기

대충 내가 이해하고 설명하기 쉬운 예를 들어 설명을 하자면,

우리는 일단 드라이브를 간다고 하자
출발점에서 도착점으로 갔다가 다시 출발점으로 돌아 온다고 했을 때,
우리가 모르는 길로 간다고 한다면, 출발점에서 도착지까지는 아무 것도 모르고 길을 따라서 일단 간다.

근데 도착지에서 출발점으로 돌아올때는 어디에서 좌회전이나 우회전을 하는지, 어디서 직진을 하는지 등에 대한 정보를 알고있다.

이유는 이미 우리는 그 길을 지나왔기 때문, 출발점에서 도착지까지의 길을 갔다왔던 것을 이용하는 것이다.

이 동적계획법이 이것과 아주 흡사하다고 생각한다.
이미 지나왔던 길은 배열에 정보를 기록해서 더 빠르고 쉽게 탐색하는 것이다.

물론 더 나은 예시를 들자면, 왕복에서 다시 출발점으로 돌아올때는 순간이동으로 돌아올 수 있다는 표현이 더 적절할 수도 있을 것 같다.

TMI

동적계획법을 처음 접하다보니 뭐가 뭔지 복잡하고 헷갈렸는데,
손으로 동작 구조를 써내려 가다 조금은 이해되는것 같기도(?)

코드

배열을 통한 동적계획법

import java.io.*;
	
public class Main {
	static Integer[][] dp = new Integer[41][2];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
	
        dp[0][0] = 1;
		dp[0][1] = 0;
		dp[1][0] = 0;
		dp[1][1] = 1;
	
		int T = Integer.parseInt(br.readLine());
	
		while(T-- > 0) {
			int N = Integer.parseInt(br.readLine());
			fibonacci(N);
			sb.append(dp[N][0] + " " + dp[N][1]).append('\n');
		}
	
		System.out.println(sb);	
	} // End of main
	
	static Integer[] fibonacci (int num) {
	
		if(dp[num][0] == null || dp[num][1] == null) {
			dp[num][0] = fibonacci(num - 1)[0] + fibonacci(num - 2)[0];
			dp[num][1] = fibonacci(num - 1)[1] + fibonacci(num - 2)[1];
		}
		
		return dp[num];
		
	} // End of fibonacci
} // End of class

반복문을 통한 동적계획법

import java.io.*;

public class Main {
	static int zero, one, zero_plus_one;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine());
		while(T-- > 0) {
			int N = Integer.parseInt(br.readLine());
			zero = 1;
			one = 0;
			zero_plus_one = 1;

			fibonacci(N);
			sb.append(zero + " " + one).append('\n');
		}

		System.out.println(sb);	
	} // End of main

	static void fibonacci (int num) {

		for(int i=0; i<num; i++) {
			zero = one;
			one = zero_plus_one;
			zero_plus_one = zero + one;
		}

	} // End of fibonacci
} // End of class