글 읽기 - 같은 로직인데 하나는 시간초과가 되고, 하나는 통과가 됩니다.

belita76 3년 전 0

먼저 글을 읽어주셔서 감사합니다!

이 문제에 대한 로직은 재귀함수로 모든 경우의 수를 탐색하는 건데요,

위 코드와 아래 코드의 로직은 같은데, 단지 함수에서 max 값을 retrurn 하느냐, 아니면 변수를 따로 선언하느냐의 차이입니다.

그런데 위의 코드는 통과 되는데 아래 코드는 시간초과가 납니다. 이유를 알 수 있을까요?

감사합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] line = br.readLine().trim().split(" ");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);
        numbers = new int[N];

        line = br.readLine().trim().split(" ");
        for(int index = 0; index<N; index++){
            numbers[index] = Integer.parseInt(line[index]);
        }


        bw.write(String.valueOf(calculateSum2(0,0,0)));
        bw.flush();
    }
    public static int N ;
    public static int M;
    public static int[] numbers;

    public static int calculateSum2(int startIndex, int sum,int count){
        if(sum>M){
            return 0;
        }
        if(count>=3){
            return sum;
        }
        if(startIndex>N){
            return 0;
        }

        int max =0;
        for(int i=startIndex;i<N;i++){
            max= Math.max(max,calculateSum2(i+1,sum+numbers[i],count+1));
        }

        return max;
    }
}

























import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] line = br.readLine().trim().split(" ");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);
        numbers = new int[N];

        line = br.readLine().trim().split(" ");
        for(int index = 0; index<N; index++){
            numbers[index] = Integer.parseInt(line[index]);
        }

        calculateSum2(0,0,0);
        bw.write(String.valueOf(max));
        bw.flush();
    }
    public static int N ;
    public static int M;
    public static int[] numbers;
    public static int max;
    public static void calculateSum(int index ,int count, int sum){
       // System.out.println("index:"+index+",count:"+count+",sum:"+sum);
        if(sum>M){
            return;
        }
        if(count>=3){
            max = Math.max(max,sum);
        }
        if(index>=N){
            return;
        }
        else{
            calculateSum(index+1, count+1, sum+numbers[index]);
            calculateSum(index+1, count, sum);
        }
    }
    public static void calculateSum2(int startIndex, int sum,int count){
        if(sum>M){
            return;
        }
        if(count>=3){
            max = Math.max(max,sum);
        }
        if(startIndex>N){
            return;
        }
        else{
            for(int i=startIndex;i<N;i++){
                calculateSum2(i+1,sum+numbers[i],count+1);
            }
        }
    }
}

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

문제

문제

출처

ICPC

같은 로직인데 하나는 시간초과가 되고, 하나는 통과가 됩니다.

belita76 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말