🏖️ 26597. 이 사람 왜 이렇게 1122를 좋아함?

문제

ZOAC 5 대회 개최를 위해 준성이가 만든 문제를 검수하던 준호는 문뜩 그런 생각이 들었다.

'이 사람 왜 이렇게 1122를 좋아함?'

하지만 사실 준성이의 최애 수는 1122가 아니다!!!

준성이의 최애 수에 대해 알려진 사실은 구간
$\left[-10^{18}, 10^{18}\right]$에 있는 정수 중 하나라는 것뿐이다.

아무래도 이 사실을 믿을 수 없는 준호는 준성이에게 최애 수가 뭔지에 대해서 질문을 하려고 한다. 질의응답은 다음과 같이 이루어진다.

준호가 구간
$\left[-10^{18}, 10^{18}\right]$에 있는 정수를 하나 제시한다.
준성이는 최애 수가 제시한 수보다 크다면 up, 작다면 down을 외친다.
준호가 제시한 수가 최애 수와 똑같은 경우는 절대 일어나지 않는다.
준호와 준성이의 검수는 아직 끝나지 않았기 때문에, 질의응답은
$Q$번만 하고 마저 검수를 하러 갔다.

대회가 시작된 지금 준호는 참가자들의 질문을 받느라 정신이 없다! 바쁜 준호를 위해 질의응답 내용을 확인하여 준성이의 최애 수를 대신 알아보도록 하자!

입력

첫째 줄에 질의응답을 진행한 횟수
$Q$가 주어진다.
$\left(1 \leq Q \leq 111\,222\right)$ 

다음
$Q$ 개의 줄에 걸쳐서 질의응답에 대한 정보가 x ^또는 x v와 같은 형태로 한 줄에 하나씩 순서대로 주어진다.
$\left(-10^{18} \leq x \leq 10^{18}\right)$ 

x ^은 준성이의 최애 수가
$x$보다 크다는 것을 의미하고, x v는 준성이의 최애 수가
$x$보다 작다는 것을 의미한다.

주어지는 수는 모두 정수다.

출력

질의응답에 모순된 내용이 있다면 첫째 줄에 Paradox!를 출력하고, 둘째 줄에 처음으로 모순이 발견된 질의응답이 몇 번째인지 출력한다.

준성이의 최애 수가 무엇인지 정확히 알아낼 수 있다면 첫째 줄에 I got it!을 출력하고, 둘째 줄에 처음으로 정확히 알아낼 수 있었던 질의응답이 몇 번째인지 출력한다.

정확히 알아낼 수 없다면 첫째 줄에 Hmm...을 출력한다.

예제 입력 1

2
3 ^
6 v

예제 출력 1

Hmm...
질의응답에 모순이 없고 준성이의 최애 숫자가 무엇인지 정확히 알 수 없으므로 첫째 줄에 Hmm...을 출력한다.

예제 입력 2

4
3 ^
6 v
5 v
2 ^

예제 출력 2

I got it!
3
질의응답에 모순이 없고 준성이의 최애 숫자가 무엇인지 정확히 알 수 있으므로 첫째 줄에 I got it!을 출력한다.
$3$번째 질의응답을 통해 준성이의 최애 숫자가 무엇인지 정확히 알 수 있으므로 둘째 줄에
$3$을 출력한다.

예제 입력 3

3
7 ^
5 v
2 v

예제 출력 3

Paradox!
2
질의응답에 모순이 있으므로 첫째 줄에 Paradox!을 출력한다.
$2$번째 질의응답에서 모순이 발견되었으므로 둘째 줄에
$2$를 출력한다.

힌트

구간
$\left[-10^{18}, 10^{18}\right]$에 있는 단 하나의 정수만 모든 질의응답에 대해 참이라면 준성이의 최애 숫자가 무엇인지 정확히 알아낼 수 있다고 한다.
구간
$\left[-10^{18}, 10^{18}\right]$에 있는 모든 정수가 모든 질의응답에 대해 거짓이라면 질의응답에 모순된 내용이 있다고 한다.
출처
University > 한양대학교 ERICA 캠퍼스 > Zero One Algorithm Contest 2022 D번

알고리즘 분류

• 구현

코드 - python3 성공

import sys
input = sys.stdin.readline

start = -1000000000000000000 # 최솟값
end = 1000000000000000000 # 최댓값

q = int(input())
index = 0

for i in range(1, q + 1):
    line = input().split()
    x = int(line[0]) # 숫자 부분 저장

    if line[1] == "^": # 최솟값 재설정
        start = max(start, x + 1)
    elif line[1] == "v": # 최댓값 재설정
        end = min(end, x - 1)

    if start == end and index == 0: # 정답 발견시 index에 저장
        index = i
    elif start > end: # 모순 발생
        print("Paradox!\n{}".format(i))
        sys.exit()

if index == 0: # 정답이 없으면
    print("Hmm...")
else: # 정답이 있으면
    print("I got it!\n{}".format(index))

---

🏖️ 6236. 용돈 관리

문제
현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.

입력

1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)

출력

첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.

예제 입력 1

7 5
100
400
300
100
500
101
400

예제 출력 1

500

알고리즘 분류

• 이분 탐색
• 매개 변수 탐색

풀이

• N일 동안 M번 인출
• K원 인출 -> 하루 사용 -> 모자라면 남은 금액 넣고 다시 K원 인출
• 무조건 횟수를 M에 맞춰야 한다.

코드 - python3 성공

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
days = []
for _ in range(N):
    days.append(int(input()))

# 모든 날에 필요한 총 금액, 최솟값, 최댓값
answer, left, right = sum(days), 0, sum(days)

# 이분탐색
while left <= right:
    mid = (left + right) // 2
    count, money = 0, 0
    lack = False # 돈이 부족한 날 체크

    # 각 날짜를 반복하며 필요한 금액 처리
    for d in days:
        if mid - d < 0:
            # 돈을 뽑아도 하루를 못 넘기면
            lack = True
            # 탐색 중지
            break
        elif money - d < 0: # 현재 소유한 금액에서 날짜에 필요한 금액을 빼고도 음수인 경우
            money = mid # 새로운 금액을 뽑아야 하므로
            count += 1 # count 증가
        money -= d # 필요한 금액을 현재 소유한 금액에서 빼준다.

    # 돈이 부족한 날이 없으면
    if not lack:
        # 목표 횟수보다 count가 같거나 작으면 돈을 줄임
        if count <= M:
            right = mid - 1
            if mid < answer:
                answer = mid
        # 목표 횟수보다 count가 크면 돈을 늘림
        elif count > M:
            left = mid + 1
    # 돈이 부족한 날이 있으면 무조건 돈을 늘림
    else:
        left = mid+1

print(answer)

참고링크

• https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search

---

🏖️ 25947. 선물할인

문제 

$n$개의 선물 가격이 주어졌을 때,
$b$의 예산으로 최대로 많은 선물을 사려고 한다. 이때 최대
$a$개의 선물에 대해서는 반값 할인을 받을 수 있다고 했을 때 최대로 살 수 있는 선물의 수를 구하는 프로그램을 작성하시오. 단, 한 선물에는 최대 한 번만 반값 할인을 받을 수 있다.

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 선물의 개수를 나타내는 양의 정수
$n$ (
$1 ≤ n ≤ 100\,000$), 예산을 나타내는 양의 정수
$b$ (
$1 ≤ b ≤ 10^9$), 반값 할인을 받을 수 있는 최대 선물의 수를 나타내는 정수
$a$ (
$0 ≤ a ≤ n$)가 공백을 사이에 두고 차례로 주어진다. 다음 줄에
$n$개의 선물 가격이 공백을 사이에 두고 주어진다. 선물 가격은
$2$이상
$10$억 이하의 값을 갖으며, 항상 짝수로 주어진다.

출력

출력은 표준출력을 사용한다. 조건을 만족하며 최대로 살 수 있는 선물의 수를 출력한다.

예제 입력 1

6 26 2
4 6 2 10 8 12

예제 출력 1

5

예제 입력 2

6 23 1
4 6 2 12 8 14

예제 출력 2

4

알고리즘 분류

• 그리디 알고리즘
• 정렬
• 누적 합

코드 - python3 성공

import sys
input = sys.stdin.readline

n, b, a = map(int, input().split()) # 선물개수, 예산, 할인 받을 수 있는 최대 선물 수
nums = list(map(int, input().split())) # 선물가격
nums.sort()

right = 0 # 현재 구매한 상품 개수
left = 0 # 할인 없이 정가로 구매한 상품 개수

for i in range(a): # 할인 상품 탐색
    b -= nums[i] // 2 # 현재 상품 가격을 반으로 나눈 값을 예산에서 뺀다. 할인 표시
    right = i + 1 # 현재까지 구매한 상품 개수 업데이트
    if b < 0: # 예산이 음수가 되면 종료
        print(i)
        sys.exit()

while right < n: # 할인 쿠폰을 모두 사용한 상태에서 추가 상품 구매
    if right - left < a: # 할인 쿠폰을 사용하지 않고 구매할 상품 개수가 할인 쿠폰 개수보다 작은 경우
        b -= nums[right] // 2 # 다음 상품의 가격을 반으로 나눈 값을 예산에서 빼고, 할인 쿠폰을 사용하지 않았음을 표시
        if b < 0:
            break
        right += 1
    else: # 반대 경우
        if a > 0:
            b -= nums[left] // 2 # 가장 낮은 가격의 상품을 반값으로 구매하고, 할인 쿠폰을 사용했음을 나타냄
            left += 1
        else:
            b -= nums[right] # 다음 상품을 정가로 구매하고, 할인 쿠폰을 사용하지 않았음
            if b < 0:
                break

print(right)