반응형

다이나믹 프로그래밍...


다이나믹 프로그래밍이라는 단어를 못봤다면 아마도 틀렸을 것이다. 백트래킹으로 문제를 풀었을 듯싶다.

그러면 시간초과나 메모리 초과가 나겠지...


풀이

1. 연속된 몇개의 숫자이다. 그러므로 연속된 값만 생각해주면 된다.

2. 두가지 경우만 생각하면된다.

이전부터 계속 연속한 값 vs 현재부터 연속된 값 의 경우를 따지면 된다.

위의 경우가 두경우를 따졌을 때, 그 위치값에서의 최대값을 나타낸 것이다.

예를 들어 10 + (-4) 의 연속된 경우와 -4부터 시작되는 경우 10 + (-4) 가 크므로 6이 된다.

그 다음 값은 10+ (-4) + 3 vs 3 인데 이때도 10 + (-4) + 3 이 크므로 dp에는 9가 저장된다.

그 다음을 계산해도 1번 + 2번 + 3번 + 4번의 값은 (4번) 보다 크므로 10이 된다.

(2번) + (3번) + (4번) or (3번) +(4번) 은 이미 이전에 계산됬기때문에 상관 안해도 된다.

이대로 가서 최대값을 찾아주면 된다.


소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
class Main {
    public static void main(String[] args) throws Exception {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        int N = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        int[] arr = new int[N];
        int[] dp = new int[N];
        int max;
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }
        dp[0] = arr[0];
        max = arr[0];
        for(int i=1; i<N; i++){
            dp[i] = Math.max(dp[i-1]+arr[i], arr[i]);
            
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
        
    }
}
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 15686 - 치킨 배달 (자바)  (0) 2018.04.16
[BOJ] 백준 15683 - 감시 (자바)  (4) 2018.04.16
[BOJ] 백준 14501 - 퇴사 (자바)  (0) 2018.03.22
[BOJ] 백준 14500 - 테트로미노 (자바)  (2) 2018.03.19
[BOJ] 백준 5014 - 스타트링크 (자바)  (0) 2018.03.19

+ Recent posts

티스토리툴바