[코틀린, 자바] 백준 25214 - 크림 파스타 (boj kotlin java)

문제 : boj25214

 

  매번 최소값과 최대값을 갱신한다고 생각해보자. 이 때 최소값이 갱신된 경우가 문제인데, 애초에 최소값이 갱신됬다고 i를 해당 값으로 선택하면 선택할 수 있는 j는 자기 자신밖에 없다(i<=j). 따라서 0이 나올수밖에 없다. 그러므로 최소값이 갱신된 경우, 이전까지 나왔던 최대 Aj - Ai 를 선택하면 된다.

 

  다음으로 최대값의 갱신쪽을 생각해보자. 이 경우 어차피 중요한건 이전까지의 Aj-Ai의 최대값이다. 그러므로 이전까지의 Aj-Ai 최대값과, 현재값-최소값 중 큰 쪽을 선택해주면 된다.

 

  즉 정리하면

1. 현재까지 나왔던 Aj-Ai의 최대값을 기록해두자 (코드에서 ans)

2. 최소값보다 현재값이 작은 경우, 현재의 최소값을 i로 두면 어차피 선택할 수 있는 j는 자기 자신뿐이라 무조건 0이다. 따라서 그냥 ans를 출력해준다.

3. 이외의 경우엔 단순히 ans와 현재값-최소값 중 큰 값을 택하면 된다.

 

코드(kotlin) : github

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    var min = Int.MAX_VALUE
    val st = StringTokenizer(readLine())
    val sb = StringBuilder()
    var ans = 0
    repeat(n) {
        val cur = st.nextToken().toInt()
        if (min > cur) min = cur
        else ans = Math.max(ans, cur-min)
        sb.append(ans).append(' ')
    }
    println(sb)
}

 

코드(java) : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int min = Integer.MAX_VALUE;
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int ans = 0;
        while (n-->0) {
            int cur = Integer.parseInt(st.nextToken());
            if (min > cur) min = cur;
            else ans = Math.max(ans, cur-min);
            sb.append(ans).append(' ');
        }
        System.out.println(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}