[백준] 1059 - 좋은 구간

www.acmicpc.net

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

🖥 시작하며

구현 문제며, 아주 약간의 수학적 사고가 가미되면 더 좋게 풀리는 문제다.

문제에서 주어진 정보는 다음과 같다.

S : 정수 집합

L : 집합 크기

n : 주어진 정수

조건을 보면,

A는 B보다 작아야 한다.

→ 입력받은 리스트를 정렬하는 것이 편할 것 같다.

A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S 에 존재하면 안 된다.

→ S 에서 찾은 n 을 포함하는 값을 찾았다고 치면, 그 S[i] 와 S[i+1] 에 각각 +1, -1 연산을 취해야 한다.

n 이 10, S 가 [4, 8, 13, 24, 30] 일 때 8, 13 사이에 n 이 들어가므로 성립한다.

또한 A = 8 + 1 = 9 , B = 13 - 1 = 12 이다.

이후에는 직접 써 가며 케이스를 탐색하거나, 직관으로 수학 공식을 구할 수 있다.

start 는 A 부터 n 까지 가능하고, end 는 n 부터 B 까지 가능한다는 것을 알 수 있다. 그러므로이라는 공식을 구할 수 있다. -1을 하는 이유는 n이 start 와 end 가 모두 되는 경우를 빼야 하기 때문이다.

⚙️ 코드


import sys

input = sys.stdin.readline


def solution(S: list, n: int) -> int:
    A, B = 0, 0

    # A와 B 찾기
    for s in S:
        if s <= n:
            A = s
        if s >= n:
            B = s
            break

    # 만약 A와 B가 같으면 (n이 범위에 포함된 경우) 0을 반환
    return 0 if A == n or B == n else (n - A) * (B - n) - 1

    # result = 0
    # # 가능한 시작점과 끝점 구간을 모두 탐색
    # for start in range(A + 1, n + 1):  # n을 포함하는 시작점
    #     for end in range(n, B):  # n을 포함하는 끝점
    #         if start < end:
    #             result += 1

    # return result


if __name__ == "__main__":
    L = int(input())
    S = list(map(int, input().rstrip().split()))
    n = int(input())

    print(solution(sorted(S), n))


#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int solution(vector<int> S, int n) {
    int A = 0, B = 0;

    // A와 B 찾기
    for (int s : S) {
        if (s <= n) {
            A = s;
        }
        if (s >= n) {
            B = s;
            break;
        }
    }

    // 만약 A와 B가 같으면 (n이 범위에 포함된 경우) 0을 반환
    if (A == n || B == n) {
        return 0;
    }

    return (n - A) * (B - n) - 1;
}

int main() {
    int L;
    cin >> L;

    vector<int> S(L);
    for (int i = 0; i < L; i++) {
        cin >> S[i];
    }

    int n;
    cin >> n;

    // S 정렬
    sort(S.begin(), S.end());

    // 결과 출력
    cout << solution(S, n) << endl;

    return 0;
}

[백준] 1059 - 좋은 구간

🖥 시작하며

⚙️ 코드

📌 소감

댓글