BOJ_16756_Pismo (Java, C++)

[Bronze I] Pismo - 16756

문제 링크

성능 요약

메모리: 2376 KB, 시간: 12 ms

분류

그리디 알고리즘, 구현

제출 일자

2024년 12월 20일 17:07:06

문제 설명

In a small village besides Đakovo lives Kasap. While agriculture is his branch, love and destiny, in his free time Kasap solves tasks in competitive programming and is doing very well. Particularly interesting are the tasks involving data structures.

On a sunny summer day, Kasap's friend Mirko sent him a letter we carry forward entirely:

“My dear Kasap,
I hope you tolerate well these hot summer days. I'm writing this letter because I have a problem. One friend gave me a hard task the other day that I have not managed to solve yet. Since I know that you love this sort of tasks, I would ask you for help because I do not want to embarass myself in front of my friend. In the task there is an array A consisting of N integers. You should find an interval of the minimum value. The value of the interval [L, R] is defined as the difference between the maximum and minimum value of the numbers in that interval: max(A[L], A[L+1], …, A[R]) - min(A[L], A[L+1], …, A[R]). I will remind you that we observe only the intervals in which L is strictly less than R.
Thank you,
Mirko”

After a week of solving, Kasap has not yet managed to solve the task and asks you to help him.

입력

In the first line of input there is a positive integer N (2 ≤ N ≤ 100 000).

In the second line of input there are N integers, which absolute value is less than 10⁹.

출력

Print the minimum value of an interval.

문제 풀이

생각보다 문제 이해가 잘 안됐다가 아이디어가 번뜩였다. 최대값 - 최소값의 차이가 최소인 구간을 찾는 것 이므로 가장 최대값 - 최소값의 차이가 적은 구간은 구간이 가장 짧을때이다. 예를들어

6
100 70 50 49 30 1 

이런 테스트케이스의 경우 최대값 - 최소값이 구간이 증가함에 따라 최댓값은 증가하고, 최솟값은 감소하기 때문에 최댓값 - 최솟값의 값 자체는 항상 구간이 증가함에 따라 커진다. 따라서 길이 2짜리에서 판별하는것이 가장 이득이다. 그리디 알고리즘이라고 생각했는데 실제로 문제 유형도 그리디였다.

코드

Java 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
//		br = new BufferedReader(new InputStreamReader(System.in));
		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int arr[] = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int res = Integer.MAX_VALUE;
		for(int i = 1; i < N; i++) {
            res=Math.min(res, Math.abs(arr[i] - arr[i-1]));
        }

		bw.write(String.valueOf(res));

		bw.flush();
		bw.close();
		br.close();
	}
}

---

C++ 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int N;
    cin >> N;
    vector<int> arr(N);

    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    int res = INT_MAX;
    for (int i = 1; i < N; i++) {
        res = min(res, abs(arr[i] - arr[i - 1]));
    }

    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}