백준 1912 연속합 [JAVA]

문제 해석

• 수열의 숫자 개수(N)만큼 숫자를 입력받고, 그 수열 중 연속된 숫자를 음수와 양수 상관없이 최댓값을 구하면 되는 문제이다.

• 2번째 예시의 과정을 풀어내면 아래와 같다.

             [예시]
              10
              2 1 -4 3 4 -4 6 5 -5 1

               solution(N-1)            m[N]           m[N]
              (1) m[0]~m[8](=9)      + m[9](=1)   vs. m[9](=1)  =>    m[0]~m[2] = 10(L)
              (2) m[0]~m[7](=14)     + m[8](=-5)  vs. m[8](=-5)  =>   m[0]~m[2] =  9(L)
              (3) m[0]~m[6](=9)      + m[7](=5)   vs. m[7](=5)  =>    m[0]~m[2] = 14(L)
              (4) m[0]~m[5](=3)      + m[6](=6)   vs. m[6](=6)  =>    m[0]~m[2] =  9(L)
              (5) m[0]~m[4](=7)      + m[5](=-4)  vs. m[5](=-4) =>    m[0]~m[5] =  3(L)
              (6) m[0]~m[3](=3)      + m[4](=4)   vs. m[4](=4)  =>    m[0]~m[4] =  7(L)
              (7) m[0]~m[2](=-1)      + m[3](=3)   vs. m[3](=3)  =>   m[0]~m[3] =  3(R)
              (8) m[0]~m[1](=3)      + m[2](=-4)  vs. m[2](=-4)  =>   m[0]~m[2] = -1(L)
              (9) m[0](=2)           + m[1](=1)   vs. m[1](=1)  =>    m[0]~m[1] =  3(L)
              (10) m[0](=2) m[0] is Not Null

                     memoArr[N]         max(초기 값 : m[0] = 2)
              (1)  memoArr[1](=3)     vs.  2 => 3(L)
              (2)  memoArr[2](=-1)    vs.  3 => 3(R)
              (2)  memoArr[3](=3)     vs.  3 => 3(L or R)
              (3)  memoArr[4](=7)     vs.  3 => 7(L)
              (4)  memoArr[5](=3)     vs.  7 => 7(R)
              (5)  memoArr[6](=9)     vs.  7 => 9(L)
              (6)  memoArr[7](=14)    vs.  9 => 14(L)
              (7)  memoArr[8](=9)     vs. 14 => 14(R)
              (8)  memoArr[9](=10)    vs. 14 => 14(R)

• 위의 과정을 통해 14라는 최댓값을 얻게 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

    static int[] numArr; //배열
    static Integer[] memoArr; //값을 저장할 배열
    static int max; //최댓값
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        numArr = new int[N];
        memoArr = new Integer[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            numArr[i] = Integer.parseInt(st.nextToken());
        }

        br.close();
        /*
          * memoArr[0]은 첫 원소로 이전에 더 이상 탐색할 것이 없기 때문에
          * numArr[0]의 값이 되기 때문에 numArr[0]으로 초기화
          * max도 첫 번째 원소로 초기화
        */
        memoArr[0] = numArr[0];
        max = numArr[0];

        //memoArr의 마지막 인덱스는 N-1이기때문에
        solution(N-1);

        System.out.println(max);
    }

    //최대 연속합을 찾는 메소드
    static int solution(int N){
        //탐색하지 않았다면,
        if(memoArr[N] == null){
            //이전 배열의 합한 값 + 현재의 값 중 최댓값을 넣는다.
            memoArr[N] = Math.max(solution(N-1) + numArr[N], numArr[N]);

            max = Math.max(memoArr[N], max);
        }

        return memoArr[N];

    }
}

결과

느낀 점

• 처음에 음수를 배제하고 보는 바람에 예시2의 출력값이 의문이 되어 좀 헤맸지만, 양수와 음수 모두 들어갈 수 있다는 것을 예시의 값을 더해보면서 알게되어 다행히 문제를 이해할 수 있었다.