[백준 / 실버3] 1003 피보나치 함수 (Java)

Ilhwanee·2022년 8월 11일
0

코딩테스트

목록 보기
81/155
post-custom-banner

문제 보기



사용한 것

  • 0과 1의 출력 횟수를 구하기 위한 bottom-up


풀이 방법

  • dp를 int형 2차원 배열 n+1, 2 크기로 생성 (dp[][0] -> 0의 수 dp[][1] -> 1의 수)
  • dp[0][0]에 1 저장 (0에서 0출력)
  • dp[1][1]에 1 저장 (1에서 1출력)
  • j = 2 부터 n 까지 for문을 돌며
    • dp[j][0]에 j-1 번째 0의 수 + j-2 번째 0의 수 저장
    • dp[j][1]에 j-1 번째 1의 수 + j-2 번째 1의 수 저장
  • 출력


코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(br.readLine());
            int[][] dp = new int[n + 1][2];
            dp[0][0] = 1;
            if(n > 0) {
                dp[1][1] = 1;
            }

            for (int j = 2; j <= n; j++) {
                dp[j][0] = dp[j - 1][0] + dp[j - 2][0];
                dp[j][1] = dp[j - 1][1] + dp[j - 2][1];
            }

            System.out.println(dp[n][0] + " " + dp[n][1]);
        }
    }
}


profile
블로그 이전 -> https://pppp0722.github.io
post-custom-banner

0개의 댓글