[HackerRank] Sherlock and Cost JAVA

 

 

🔗 HackerRank Sherlock and Cost https://www.hackerrank.com/challenges/sherlock-and-cost/problem

문제

In this challenge, you will be given an array $B$ and must determine an array $A$.

There is special rule: For all $i$, $A$[$i$] $\leq$ $B$[$i$].

That is, $A$[$i$] can be any number you choose such that 1 $\leq$ $A$[$i$] $\leq$ $B$[$i$].

Your task is to select a series of $A$[$i$] given $B$[$i$] such that the sum of the absolute difference of consecutive pairs of $A$ is maximized.

This will be the array's cost, and will be represented by the variable $S$ below.

 

The equation can be written:

$$S = \sum_{i=2}^N |A[i] - A[i - 1]|$$

 

For example, if the array $B$ $=$ $[1, 2, 3]$, we know that $1$ $\leq$ $A[1]$ $\leq$ $1$, $1$ $\leq$ $A[2]$ $\leq$ $2$, and $1$ $\leq$ $A[3]$ $\leq$ $3$.

Arrays meeting those guidelines are:

[1,1,1], [1,1,2], [1,1,3]
[1,2,1], [1,2,2], [1,2,3]

 

Our calculations for the arrays are as follows:

|1-1| + |1-1| = 0	|1-1| + |2-1| = 1	|1-1| + |3-1| = 2
|2-1| + |1-2| = 2	|2-1| + |2-2| = 1	|2-1| + |3-2| = 2

 

The maximum value obtained is $2$.

 

Function Description

Complete the cost function is the editor below. It should return the maximum value that can be obtained.

 

cost has the following parameter(s):

• B: an array of Integers

Input Format

The first line contains the integer $t$, the number of test cases.

Each of the nest $t$ pairs of lines is a test case where:

- The first line contains an integer $n$, the length of $B$

- The next line contains $n$ space-separated integers $B[i]$

 

Constraints

• $1$ $\leq$ $t$ $\leq$ $20$
• $1$ $<$ $n$ $\leq$ $10^5$
• $1$ $\leq$ $B[i]$ $\leq$ $100$

Output Format

For each test case, print the maximum sum on a separate line.

 

Sample Input

1
5
10 1 10 1 10

 

Sample Output

36

 

Explanation

The maximum sum occurs when A[1]=A[3]=A[5]=10 ans A[2]=A[4]=1. That is

$|1 - 10| + |10 -1| + |1 - 10| + |10 - 1| = 36.$

---

풀이

주어진 B 배열로 A 배열을 만드는 데, A의 모든 요소들의 $|A[i] - A[i - 1]|$의 합이 최대인 경우 그 값을 리턴시키는 문제였다.

일단 문제에 주어진 조건이 $1 \leq A[i] \leq B[i]$ 였기에

$A[i]$는 1 혹은 $B[i]$만이 될 수 있다.

만약, B 배열이 [30, 30, 30]이라면 A 배열이 [30, 1, 30] 일 때 최대값이 나온다.

|1 - 30| + |1 - 30| = 58

 

이 문제에서 bfs, dfs를 사용하여 brute-force를 하게 되면 시간제한에 걸리게 된다.

그렇기에 Dynamic Programming을 사용하였다.

Math.max를 사용하며 절대값의 연산을 내부에서 미리 실행하여 값을 순차적으로 저장하였다.

 

내가 푼 코드

class Result {

    /*
     * Complete the 'cost' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY B as parameter.
     */

    public static int cost(List<Integer> B) {
    // Write your code here
        int[][] S = new int[B.size()][2];
        for(int i = 1; i < B.size(); i++) {
            S[i][0] = Math.max(S[i - 1][0],S[i - 1][1] + B.get(i - 1) - 1);
            S[i][1] = Math.max(S[i - 1][1], S[i - 1][0] + B.get(i) -1);
        }
        return Math.max(S[B.size() - 1][0], S[B.size() - 1][1]);
    }

}