글 읽기 - 파도반 수열 뭐가 문제일까요?[배열 크기 선언]

kwon5891 3년 전 0

20,22 번째 라인에서 배열을 하나 선언하는데요 입력값에 따라 메모리 크기를 바꿔주려고

테스트 케이스로 들어온 N중에 가장 큰 값을 가지고 P 배열의 그 최댓값을 가지는 N의 인덱스 만큼만 값을 구하고 값을 출력하도록 코드를 짰습니다.

( 테스트 케이스중 가장 큰값까지 구하면 나머지 테스트 케이스는 dp기 때문에 이미 계산되어 있으므로 배열을 저 이상 할당할 필요가 없다고 생각하였습니다)

P = new long[max+1] 이런식으로 짰습니다.

이렇게 해놓고 제가 직접 테스트 돌리니까 N=100일때도 정답이 잘 나오더라구요.

그래서 제출을 했는데 틀렸다고 뜨네요.

그래서 뭔지 한참을 찾아도 뭐가 틀린지 모르겠어서 검색해보니까 다른 정답 코드들은 그냥 P = new long[101]로 처음부터 선언할때 최댓값으로 선언을 하셨길래

저도 101로 바꿔서 해보았는데 정답입니다! 가 뜨더라구요.. 저는 왜 이 차이가 정답과 실패를 만드는지 궁금합니다.

알려주시면 정말 감사하겠습니다.

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int test_num = scanner.nextInt();
        int[] N = new int[test_num];
        int max = 0;
        long[] P;
        for(int i = 0 ; i < test_num; i++){
            N[i] = scanner.nextInt();
            if(max < N[i]){
                max = N[i];
            }
        }
        if(max <= 5){
            P = new long[6];
            P[1] = 1; P[2] =1; P[3]=1; P[4] =2; P[5]=2;
        }
        else{
            P = new long[max];  // 이부분 선언
            P[1] = 1; P[2] =1; P[3]=1; P[4] =2; P[5]=2;
            int[] count = new int[max]; // 이부분 선언
            count[1] =1; count[2] =1; count[3] =1; count[4] =1; count[5] = 2;
            int availabe_min = 1;

            for(int i = 6; i <= max; i++){
                count[i] = 2;
                if (count[availabe_min] <= 0) {
                    availabe_min++;
                }
                P[i] = P[i-1] + P[availabe_min];
                count[availabe_min]--;
                count[i-1]--;
            }
        }

        for(int i : N){
            System.out.println(P[i]);
        }
    }
}

plan222 3년 전 0

인덱스를 1~max까지 사용하시니까 배열 크기는 max+1개를 잡아야 합니다.

P = new long[max] 이렇게 하면 P[max-1]까지 밖에 못쓰겠죠?

제가 자바를 잘 몰라서 왜 100인 경우에 정상적으로 출력되었는지는 잘 모르겠습니다.

댓글을 작성하려면 로그인해야 합니다.