[백준][Java] 1744 - 수 묶기

문제 정보

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

난이도 : G4

유형 : DP

시간 : O(N), 정렬시간 제외

---

해결 방법

모든 수는 최대 한 번만 묶일 수 있다.
연속이 아닌 부분 수열의 합을 구하는 것이므로 수열의 원소의 위치가 변경돼도 상관없다. -> 정렬 가능

 

1. 직관적으로 큰 수끼리 곱해야 더 큰 수가 나오므로 주어진 수열을 정렬한다.

2. 오름차 순으로 정렬 시 왼쪽에서부터 오른쪽으로 진행

3. 탐색하면서 매 순간 dp배열에 가장 큰 값을 대입한다.

 

dp배열은 매 탐색 중 가장 큰 값이 저장된 배열이다.
더 큰 수를 선택하기 위해서 2가지를 고려해야한다.

 

1. 수열[i] 와 수열[i-1]  곱  + dp[i - 2] 

2. 수열[i] + dp[i-1]

 

쉽게 말하자면

현재 수를 왼쪽 수와 묶었을 때와 묶지 않았을 때의 값 중 큰 값을 선택하면 된다.

 

현재 수와 왼쪽 수를 묶었을 때 우리는 왼쪽 수의 이전 값의 가장 큰 값만 알면 되고

현재 수를 묶지 않을 때는 왼쪽 수까지의 가장 큰 값만 알면 된다.

 

코드

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

public class Main {

    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N;
    int[] sequence;
    int[] dp;

    private void solution() throws IOException {

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

        if (N == 1) {
            System.out.println(Integer.parseInt(br.readLine()));
            return;
        }

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

        Arrays.sort(sequence);

        dp = new int[N + 1];
        dp[1] = sequence[0];

        for (int i = 2; i <= N; i++) {
            dp[i] = Math.max(dp[i - 1] + sequence[i - 1], dp[i - 2] + sequence[i - 2] * sequence[i - 1]);
        }

        System.out.println(dp[N]);
    }

    public static void main(String[] args) throws IOException {

        Main main = new Main();
        main.solution();
    }
}