[백준] 9461번: 파도반 수열

가영·2021년 1월 22일
0

알고리즘

목록 보기
3/41
post-thumbnail

쉬운 문제였다. 수열의 점화식을 바로 찾아서 재귀함수 p(n)을 만들었다. 초기값만 정해주고 돌리면 예제의 답이 잘 나왔다. 근데 또 채점만 하면 틀렸다는거다.

아무리 봐도 내가 맞는데 계속 틀려서 화가 나서 자고 일어났다. 에이용한테두 물어봤지만 에이용도 나랑 똑같이 틀렸다. 허무하고 현타왔다. 근데 시간 좀 지나서 에이용이 타입 바꾸고 맞았다고 했다. 왜 그 생각을 못했지? 나도 dp 타입을 long으로 바꾸니까 바로 맞았다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class boj9461 {
    static long[] dp; // 나는 여기서 int배열로 선언해서 틀림
    public static long p(int n) {
        if(dp[n] != 0)
            return dp[n];
        return dp[n] = p(n-5) + p(n-1);
    }
    public static void main(String[] args) {
        try {
            dp = new long[100+1];
            dp[1] = dp[2] = dp[3] = 1;
            dp[4] = dp[5] =2;
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(br.readLine());
            int[] N = new int[T];
            for(int i = 0; i < T; i++) {
                N[i] = Integer.parseInt(br.readLine());
            }
            for(int i = 0; i < T; i++) {
                System.out.println(p(N[i]));
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

친구 답

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long[] dp = new long[101];
        dp[1] = dp[2] = dp[3] = 1;
        dp[4] = dp[5] = 2;

        int input;
        int T = sc.nextInt();

        for(int j = 6; j <= 100; j++) {
            if(dp[j] == 0)
                dp[j] = dp[j - 1] + dp[j - 5];
        }

        for(int i = 0; i < T; i++) {
            input = sc.nextInt();

            System.out.println(dp[input]);
        }
    }
}

해결책: 답을 저장할 때는 타입도 좀 생각해라

0개의 댓글