1 분 소요

1. 문제

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

  • 정렬 문제
// 문제
정수 집합 S가 주어졌을때, 
다음 조건을 만족하는 구간 [A, B] 좋은 구간이라고 한다.

A와 B는 양의 정수이고, A < B를 만족한다.
A  x  B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.
집합 S와 n이 주어졌을 , n을 포함하는 좋은 구간의 개수를 구해보자.

// 입력
첫째 줄에 집합 S의 크기 L이 주어진다. 
둘째 줄에는 집합에 포함된 정수가 주어진다. 
셋째 줄에는 n이 주어진다.

// 출력
첫째 줄에 n을 포함하는 좋은 구간의 개수를 출력한다.

// 제한
1  L  50
집합 S에는 중복되는 정수가 없다.
집합 S에 포함된 모든 정수는 1보다 크거나 같고, 1,000보다 작거나 같다.
1  n  (집합 S에서 가장  정수)

// 예제 입력 1 
4
1 7 14 10
2

// 예제 출력 1 
4 // [2,3], [2,4], [2,5], [2, 6]

// 예제 입력 2 
5
4 8 13 24 30
10

// 예제 출력 2 
5 // [9, 10], [9, 11], [9, 12], [10, 11], [10, 12]

// 예제 입력 3 
5
10 20 30 40 50
30

// 예제 출력 3 
0

// 예제 입력 4 
8
3 7 12 18 25 100 33 1000
59

// 예제 출력 4 
1065


2. 핵심 아이디어

  • 규칙 잘 찾아내기


3. Python 문제풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
t = int(input())

arr.append(0)
arr.sort()

result = 0
for i in range(len(arr) - 1) :
  if arr[i] == t or arr[i+1] == t:
    result = 0
    break
  elif arr[i] < t and t < arr[i+1] :
    result = (t - arr[i]) * (arr[i+1] - t) - 1
    break

print(result)


4. Java 문제풀이


댓글남기기