[백준 1183] 약속 (C++) - S2

문제

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

1183번: 약속

 

개요

실버 랜덤 디펜스를 처음 시작했다.

PS가 습관이 되지 않아 뭔가 새로운 자극이 필요했고, DP, 그리디 등의 알고리즘 분류를 모르는 채로 문제를 맞닥뜨린 채로 문제를 풀 수 있는 랜덤 디펜스를 습관 들이기로 했다.

실버 랜덤 디펜스가 정상적으로 습관화되고, 실버 문제를 빠른 시간 내에 정확히 푸는 실력이 갖추어지면 그 때 골드 랜덤 디펜스로 넘어가야겠다고 생각했다.

 

실랜디를 시작하고 맞이한 첫 문제였는데, 문제 소개부터 잘 이해가 되지 않아 생각보다 당황했다.

계속 생각해봐도 적절한 풀이를 찾지 못해 결국 구글링을 했다..! 생각보다 수학적인 지식이 필요한 문제였다.

내 나름대로의 풀이를 정리해보도록 하겠다.

 

문제 풀이

위의 식의 결과값을 최소로 만드는 정수 T 개수를 구해야 한다.

 

Ai , Bi 의 값은 주어지기 때문에 사실상 Ai - Bi 는 정수 값이다.

따라서, 절댓값 기호 내부는 T가 변수인 일차방정식 형태인 것이다.

 

실제로, 그래프를 그려보면, 규칙을 찾기 쉽다.

 

(i) y = |x - 2|

N = 1인 경우이다.

최솟값을 갖는 x 값은 x = 2, 하나이다.

 

(ii) y = |x - 2| + |x - 4|

N = 2인 경우이다.

최솟값을 갖는 x 값은 x = 2, 3, 4, 총 3개이다. (2 이상 4 이하의 정수들)

2는 [2, 4] 배열에서 (2 / 2) - 1 = 0번째 index의 값이고, 4는 2 / 2 = 1번째 index의 값이다.

즉, 정렬된 배열에서 (N / 2) - 1 번째 index의 값부터 N / 2 번째 index의 값까지의 개수이다.

 

(iii) y = |x - 2| + |x - 4| + |x - 6|

N = 3인 경우이다.

최솟값을 갖는 x 값은 x = 4, 하나이다. (4는 2, 4, 6의 중앙값)

 

(iv) y = |x - 2| + |x - 4| + |x - 8| + |x - 10|

N = 4인 경우이다.

최솟값을 갖는 x 값은 x = 4, 5, 6, 7, 8, 총 5개이다. (4 이상 8 이하의 정수들)

4는 [2, 4, 8, 10] 배열에서 (4 / 2) - 1 = 1번째 index의 값이고, 8은 4 / 2 = 2번째 index의 값이다.

즉, 정렬된 배열에서 (N / 2) - 1 번째 index의 값부터 N / 2 번째 index의 값까지의 개수이다.

 

정리하면,

N이 홀수인 경우에는 T의 개수는 1개이다. (정렬된 배열에서의 중앙값)

N이 짝수인 경우에는 T의 값은 정렬된 배열에서 (N / 2) - 1 번째 index의 값부터 N / 2 번째 index의 값까지의 개수이다.

 

코드

C++ 코드

#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#include <bitset>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	vector <int> v;
	for (int i = 0; i < n; i++) {
		int a, b; cin >> a >> b;
		v.push_back(a - b);
	}
	sort(v.begin(), v.end());

	if (n % 2 == 1) cout << 1;
	else cout << v[n / 2] - v[n / 2 - 1] + 1;

	return 0;
}

 

JAVA 코드

import java.io.*;
import java.util.*;

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        List<Integer> list = new ArrayList<>();
        for (int i = 0 ; i < n; i++){
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            list.add(a - b);
        }
        Collections.sort(list);

        // BufferedWriter 에 정수형 넣고 싶으면 String 타입으로 변환 필요
        int result = 1;
        if (n % 2 == 0)
            result = list.get(n / 2) - list.get(n / 2 - 1) + 1;

        bw.write(Integer.toString(result));

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

}

 

추가 설명

값이 겹치는 경우엔 어떡하지? 라는 의문이 들 수 있다.

예를 들면, y = |x - 2| + |x - 2| + |x - 6| 와 같은 경우이다.

N = 3 이므로 홀수인 경우로 적용해야 하는가, 아니면 중복되는 2를 제외하면 2와 6, 총 2개이니까 짝수인 경우로 적용해야 하는가? 라는 의문이 들 수 있다.

 

y = |x - 2| + |x - 2| + |x - 6| 그래프는 다음과 같다.

최솟값을 갖는 x 값은 x = 2, 하나이다.

즉, 기존 규칙대로 N이 홀수인 경우로 적용되는 것을 알 수 있다.

N이 짝수인 경우로 실험해봐도 마찬가지이다.

 

결론은, 배열에 중복 값이 있어도 신경쓰지 않고 기존의 규칙을 적용하면 된다.

 

깨달은 점

이렇게 수학적인 지식을 요구하는 문제가 나오면 항상 쉽지 않은 것 같다.

물론, 수학 지식을 모르는 상태에서도 어쩌저찌 풀 수는 있겠지만, 알고있는 상태에서 푸는 것이랑은 시간이나 효율성 측면에서 비교가 안 될 것이다.

시간 날 때마다 틈틈이 PS에 자주 등장하는 수학 공식들을 보는 습관을 들여야겠다.

 

그리고, 코딩테스트에 C++을 사용할 수 없고, JAVA만 사용할 수 있는 경우가 꽤 있다고 해서, 일단 먼저 C++로 문제를 풀고, 똑같은 풀이를 JAVA로 다시 쓰는 연습을 하고 있다.

항상 드는 생각이지만, JAVA는 PS용 언어는 정말 아닌 것 같다.

동일한 코드여도 코드의 길이도 길고, 직관적이지 않은 느낌이다.

 

이 문제를 시작으로, 실버 랜덤 디펜스를 꾸준히 해야겠다.