[백준] 3020번 개똥벌레
2021-03-20
Algorithm / Python

[백준] 3020번 개똥벌레

출처: [백준] 3020번 개똥벌레

문제

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

img

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

img

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

출력

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

예제 출력 1

1
7 2

힌트

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2007 > Croatian Regional Competition in Informatics 2007 3번

Olympiad > Croatian Highschool Competitions in Informatics > 2007 > Regional Competition - Juniors 4번

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: citizen

알고리즘 분류

풀이

소스코드

Using Bisect

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import sys
from bisect import bisect_left

input = sys.stdin.readline

N, H = map(int, input().split())

down = []
up = []
for i in range(N):
    if i % 2 == 0:  # 짝수: 석순
        down.append(int(input()))
    else:
        up.append(int(input()))

down.sort()
up.sort()

min_count = N
result = 0

for i in range(1, H + 1):
    down_count = len(down) - bisect_left(down, i - 0.5)
    up_count = len(up) - bisect_left(up, H - i + 0.5)

    if min_count == down_count + up_count:
        result += 1
    elif min_count > down_count + up_count:
        result = 1
        min_count = down_count + up_count

print(min_count, result)

non Bisect

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import sys

input = sys.stdin.readline

N, H = map(int, input().split())

down = []
up = []
for i in range(N):
    if i % 2 == 0:  # 짝수: 석순
        down.append(int(input()))
    else:
        up.append(int(input()))

down.sort()
up.sort()


def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return start


min_count = N
result = 0

for i in range(1, H + 1):
    down_count = len(down) - binary_search(down, i - 0.5, 0, len(down) - 1)
    up_count = len(up) - binary_search(up, H - i + 0.5, 0, len(up) - 1)

    if min_count == down_count + up_count:
        result += 1
    elif min_count > down_count + up_count:
        result = 1
        min_count = down_count + up_count

print(min_count, result)

[백준] 2798번 블랙잭
2021-03-07
Algorithm / Python

[백준] 2798번 블랙잭

출처: [백준] 2798번 블랙잭

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 61157 27608 21782 44.404%

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

예제 입력 1

1
2
5 21
5 6 7 8 9

예제 출력 1

1
21

예제 입력 2

1
2
10 500
93 181 245 214 315 36 185 138 216 295

예제 출력 2

1
497

출처

알고리즘 분류

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
from itertools import combinations

input = sys.stdin.readline

n, m = map(int, input().split())
cards_list = list(map(int, input().split()))

result = list(combinations(cards_list, 3))

max_sum = 0
for cards in result:
    temp_sum = sum(cards)
    if m >= temp_sum > max_sum:
        max_sum = temp_sum

print(max_sum)

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
cards_list = list(map(int, input().split()))

max_sum = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(j + 1, N):
            if M >= cards_list[i] + cards_list[j] + cards_list[k] > max_sum:
                max_sum = cards_list[i] + cards_list[j] + cards_list[k]

print(max_sum)

팔로우

카테고리

최근 글

태그

알고리즘190
Python182
백준172
IT뉴스92
IT Issues92
구현65
자료구조55
네이버39
카카오30
스택26
JS24
Javascript24
자바스크립트24
큐22
문자열20
수학16
Programming16
애플15
그래프 탐색15
해시15
핀테크14
너비 우선 탐색14
BFS14
프로그래머스14
Spring Boot14
Java14
그래프13
DFS13
구글12
그리디12
×