i can do ik!

BOJ 14720 우유 축제

문제

영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다.

입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다.

    1. 맨 처음에는 딸기우유를 한 팩 마신다.
    2. 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다.
    3. 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다.
    4. 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다. 

영학이는 우유 축제가 열리고 있는 우유거리에 왔다. 

우유 거리에는 우유 가게들이 일렬로 늘어서 있다.

영학이는 우유 거리의 시작부터 끝까지 걸으면서 우유를 사먹고자 한다.

각각의 우유 가게는 딸기, 초코, 바나나 중 한 종류의 우유만을 취급한다.

각각의 우유 가게 앞에서, 영학이는 우유를 사마시거나, 사마시지 않는다.

우유거리에는 사람이 많기 때문에 한 번 지나친 우유 가게에는 다시 갈 수 없다.

영학이가 마실 수 있는 우유의 최대 개수를 구하여라.

시간 제한 : 1 초
메모리 제한 : 256 MB

입력

첫째 줄에 우유 가게의 수 N이 주어진다. (1 ≤ N ≤ 1000)

둘째 줄에는 우유 가게 정보가 우유 거리의 시작부터 끝까지 순서대로 N개의 정수로 주어진다.

0은 딸기우유만을 파는 가게, 1은 초코우유만을 파는 가게, 2는 바나나우유만을 파는 가게를 뜻하며, 

0, 1, 2 외의 정수는 주어지지 않는다.

출력

영학이가 마실 수 있는 우유의 최대 개수를 출력하시오.

예제 입력 1

7
0 1 2 0 1 2 0

예제 출력 1

7

풀이

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

for i in range(n) : 
    if arr[i] == cnt % 3 :	
        cnt += 1

print(cnt)

BOJ 10994 별 찍기 - 19

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

시간 제한 : 1 초
메모리 제한 : 256 MB

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 차례대로 별을 출력한다.

예제 입력 1

1

예제 출력 1

*

예제 입력 2

2

예제 출력 2

*****
*   *
* * *
*   *
*****

예제 입력 3

3

예제 출력 3

*********
*       *
* ***** *
* *   * *
* * * * *
* *   * *
* ***** *
*       *
*********

예제 입력 4

4

예제 출력 4

*************
*           *
* ********* *
* *       * *
* * ***** * *
* * *   * * *
* * * * * * *
* * *   * * *
* * ***** * *
* *       * *
* ********* *
*           *
*************

풀이

n = int(input())
star = [[' ' for _ in range(4 * n - 3)] for _ in range(4 * n - 3)]

def draw_star(n, x, y):
    if n == 1:
        star[y][x] = '*'
        return
    
    length = 4 * n -3

    for i in range(length):
        star[y][x+i] = '*'
        star[y+i][x] = '*'
        star[y+length-1][x+i] = '*'
        star[y+i][x+length-1] = '*'
    
    draw_star(n-1, x+2, y+2)

draw_star(n, 0, 0)

for j in star:
    print(''.join(j))

BOJ 11508 2+1 세일

문제

KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. 

KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 

나머지 두 개의 제품 가격만 지불하면 됩니다. 

한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 합니다.

예를 들어, 7개의 유제품이 있어서 각 제품의 가격이 10, 9, 4, 2, 6, 4, 3이고 

재현이가 (10, 3, 2), (4, 6, 4), (9)로 총 3번에 걸쳐서 물건을 산다면 첫 번째 꾸러미에서는 13원을,

두 번째 꾸러미에서는 10원을, 세 번째 꾸러미에서는 9원을 지불해야 합니다.

재현이는 KSG 편의점에서 친구들과 같이 먹을 총 N팩의 유제품을 구입하려고 합니다. 

재현이를 도와 최소비용으로 유제품을 구입할 수 있도록 도와주세요!

시간 제한 : 1 초 
메모리 제한 : 64 MB

입력

첫 번째 줄에는 유제품의 수 N (1 ≤ N ≤ 100,000)이 주어집니다.

두 번째 줄부터 N개의 줄에는 각 유제품의 가격 Ci (1 ≤ Ci ≤ 100,000)가 주어집니다.

출력

재현이가 N개의 유제품을 모두 살 때 필요한 최소비용을 출력합니다. 정답은 231-1보다 작거나 같다.

예제 입력 1

4
3
2
3
2

예제 출력 1

8

예제 입력 2

6
6
4
5
5
5
5

예제 출력 2

21

풀이

import sys 

input = sys.stdin.readline
arr = []
n = int(input())

for i in range(n):
    arr.append(int(input()))

arr.sort(reverse = True)
res = 0

for i in range(n):
    if i % 3 != 2:
        res += arr[i]

print(res)

BOJ 7795 먹을 것인가 먹힐 것인가

문제

심해에는 두 종류의 생명체 A와 B가 존재한다. 

A는 B를 먹는다.

A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 

예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 

A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, 

A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 

각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다.

둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 

크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000)

출력

각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

예제 입력 1

2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215

예제 출력 1

7
1

풀이

import sys

input = sys.stdin.readline
t = int(input())

def binary_search(target, data):
    start = 0
    end = len(data) - 1
    res = -1
    while start <= end:
        mid = (start+end) // 2
        if data[mid] < target:
            res = mid
            start = mid + 1
        else:
            end = mid -1
    return res

for _ in range(t):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a.sort()
    b.sort()
    cnt = 0
    
    for i in a:
        cnt += binary_search(i, b) + 1

    print(cnt)

BOJ 1330 K번째 수

문제

세준이는 크기가 N×N인 배열 A를 만들었다.

배열에 들어있는 수 A[i][j] = i×j 이다. 

이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. 

B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

시간 제한 : 2 초
메모리 제한 : 128 MB

입력

첫째 줄에 배열의 크기 N이 주어진다.

N은 105보다 작거나 같은 자연수이다.

둘째 줄에 k가 주어진다. 

k는 min(109, N2)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

예제 입력 1

3
7

예제 출력 1

6

풀이

import sys

input = sys.stdin.readline
n = int(input())
k = int(input())
start = 1
end = k

while start <= end:
    mid = (start + end) // 2
    cnt = 0

    for i in range(1, n + 1):
        cnt += min(mid // i, n)  
 
    if cnt >= k:
        res = mid
        end = mid - 1
    else:
        start = mid + 1

print(res)

BOJ 2512 예산

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다.

국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 

그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.

2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 
상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 

이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 

그 합이 484로 가능한 최대가 된다. 

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 

위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

시간 제한 : 1 초
메모리 제한 : 128 MB

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. 

N은 3 이상 10,000 이하이다. 

다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 

이 값들은 모두 1 이상 100,000 이하이다. 

그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. 

M은 N 이상 1,000,000,000 이하이다.

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.

예제 입력 1

4
120 110 140 150
485

예제 출력 1

127

예제 입력 2

5
70 80 30 40 100
450

예제 출력 2

100

풀이

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

def budget(arr):
    start = 0
    end = max(arr)

    while start <= end :
        mid = (start + end) // 2
        cnt = 0

        for i in range(n) :
            if arr[i] >= mid :
                cnt += mid
            else :
                cnt += arr[i]

        if cnt <= m :
            start = mid + 1
        else :
            end = mid - 1
    return end

print(budget(arr))

BOJ 2110 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 

각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 

최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 

가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 

가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

시간 제한 : 2 초
메모리 제한 : 128 MB

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 

둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

예제 입력 1

5 3
1
2
8
4
9

예제 출력 1

3

힌트

공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 

이 거리보다 크게 공유기를 3개 설치할 수 없다.

풀이

import sys

input = sys.stdin.readline
n, c = map(int, input().split())
house = []

for _ in range(n):
    house.append(int(input()))

house.sort()
start = 1
end = house[-1] - house[0]
res = 0

while start <= end:
    mid = (start + end) // 2
    cnt = 1
    tmp = house[0]
    
    for i in range(1, n):
        if house[i] >= tmp + mid:
            cnt += 1
            tmp = house[i]

    if cnt < c:
        end = mid - 1
    else:
        start = mid + 1
        res = mid

print(res)

BOJ 1654 랜선 자르기

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 

박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 

그러나 K개의 랜선은 길이가 제각각이다. 

박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 

예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다.(이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 

기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 

그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. 

N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 

이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

시간 제한 : 2 초
메모리 제한 : 128 MB

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. 

K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다.

그리고 항상 K ≦ N 이다.

그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 

랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

예제 입력 1

4 11
802
743
457
539

예제 출력 1

200

힌트

802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개, 539cm 랜선에서 2개를 잘라내 모두 11개를 만들 수 있다.

풀이

import sys

input = sys.stdin.readline
k, n = map(int, input().split())
cable = []

for _ in range(k):
    cable.append(int(input()))

cable.sort()
maxLength = 0

def cut_cable(target, start, end):
    global maxLength
    count = 0
    mid = (start + end) // 2
    
    if start > end:
        return None
    for i in cable:
        count += i // mid
    if count >= target:
        maxLength = max(maxLength, mid)
        return cut_cable(target, mid+1, end)
    elif count < target:
        return cut_cable(target, start, mid-1)

result = cut_cable(n, 1,max(cable))

print(maxLength)