[Java] 백준 - 1912번: 연속합

5월 15일(월) - 동적 계획법 1 (1912번)

1912번: 연속합

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. BufferedReader 다음에 StringTokenizer 부분을 바로 이어서 작성했을 때 NumberFormatException 이 발생

-> StringTokenizer 부분을 아래의 풀이 - 1처럼 for문 바로 위에 위치시켰더니 정상 작동

-> 이유 더 알아봐야함

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

( C언어 풀이 그대로 활용 )

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

import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int n = Integer.parseInt(br.readLine());
        int[] num = new int[n+1];
        int[] tmp_sum = new int[n+1];

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=1; i<n+1; i++)
        {
            num[i] = Integer.parseInt(st.nextToken());
        }

        tmp_sum[1] = num[1];
        for(int i=2; i<n+1; i++)
        {
            if((tmp_sum[i-1] + num[i]) < num[i])
            {
                tmp_sum[i] = num[i];
            }
            else
            {
                tmp_sum[i] = tmp_sum[i-1] + num[i];
            }
        }

        int max = -1000000;
        for(int i=1; i<n+1; i++)
        {
            if(max < tmp_sum[i])
            {
                max = tmp_sum[i];
            }
        }

        System.out.println(max);
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

( Math.max 활용하여 간단하게 정리한 풀이)

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

import java.util.StringTokenizer;

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());
        int[] num = new int[n+1];
        int[] tmp_sum = new int[n+1];

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=1; i<n+1; i++)
        {
            num[i] = Integer.parseInt(st.nextToken());
        }

        tmp_sum[1] = num[1];
        for(int i=2; i<n+1; i++)
        {
            tmp_sum[i] = Math.max(tmp_sum[i-1] + num[i], num[i]);
        }

        int max = -1000000;
        for(int i=1; i<n+1; i++)
        {
            max = Math.max(tmp_sum[i], max);
        }

        System.out.println(max);
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ