i can do ik!

BOJ 1072 게임

문제

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 

형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 

누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 

의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 

그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.

이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 

하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.

게임 기록은 다음과 같이 생겼다.

게임 횟수 : X
이긴 게임 : Y (Z%)
Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.

X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.

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

입력

각 줄에 정수 X와 Y가 주어진다.

출력

첫째 줄에 형택이가 게임을 최소 몇 판 더 해야하는지 출력한다. 

만약 Z가 절대 변하지 않는다면 -1을 출력한다.

제한

1 ≤ X ≤ 1,000,000,000
0 ≤ Y ≤ X

예제 입력 1

10 8

예제 출력 1

1

예제 입력 2

100 80

예제 출력 2

6

예제 입력 3

47 47

예제 출력 3

-1

예제 입력 4

99000 0

예제 출력 4

1000

예제 입력 5

1000000000 470000000

예제 출력 5

19230770

풀이

import sys

input = sys.stdin.readline
x , y = map(int, input().rstrip().split())
z = (y * 100) // x
res = 0

if z >= 99:
    print(-1)
else:
    res = 0
    start = 1
    end = 1000000000

    while start <= end:
        mid = (start + end)//2
        if (y + mid) * 100 // (x + mid) > z:
            res = mid
            end = mid-1
        else:
            start = mid+1
    print(res)

BOJ 2352 반도체 설계

문제

반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.

예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 

하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다.

n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 

연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오

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

입력

첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다.

다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 

이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

출력

첫째 줄에 최대 연결 개수를 출력한다.

예제 입력 1

6
4 2 6 3 1 5

예제 출력 1

3

풀이

import sys
import bisect

input = sys.stdin.readline
n = int(input())
port = list(map(int, input().split()))
res = [port[0]]

for i in range(1, n):
    if port[i] > res[-1]:
        res.append(port[i])
    else:
        idx = bisect.bisect_left(res, port[i])
        res[idx] = port[i]

print(len(res))

BOJ 12738 가장 긴 증가하는 부분 수열 3

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

시간 제한 : 3 초
메모리 제한 : 512 MB

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

풀이

import sys
import bisect

input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
res = [arr[0]]

for i in range(1, n):
    if arr[i] > res[-1]:
        res.append(arr[i])
    else:
        index = bisect.bisect_left(res, arr[i])
        res[index] = arr[i]

print(len(res))

BOJ 3020 개똥벌레

문제

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 

동굴의 길이는 N미터이고, 높이는 H미터이다. 

(N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

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

이 개똥벌레는 장애물을 피하지 않는다. 

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

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다.

(4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

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

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 

이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

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

입력

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

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

출력

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

예제 입력 1

6 7
1
5
3
3
5
1

예제 출력 1

2 3

예제 입력 2

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

예제 출력 2

7 2

풀이

import sys
import bisect

input = sys.stdin.readline
n, h = map(int, input().split())
top = []
bot = []

for i in range(n):
    if i % 2 == 0:
        bot.append(int(input()))
    else:
        top.append(h-int(input()))
top.sort()
bot.sort()
res = n
cnt = 0

for i in range(h):
    top_idx = bisect.bisect_right(top, i)
    bot_idx = bisect.bisect_right(bot, i)
    cur = top_idx + len(bot) - bot_idx
    if res == cur:
        cnt += 1
    elif res > cur:
        res = cur
        cnt = 1

print(res, cnt)

BOJ 14003 가장 긴 증가하는 부분 수열 5

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

시간 제한 : 3 초
메모리 제한 : 512 MB

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4
10 20 30 50

풀이

from bisect import bisect_left

n = int(input())
arr = [0] + list(map(int,input().split()))
d = [0] * (n+1) 
cmp = [-1000000001] 
tmp = 0

for i in range(1, n+1):
    if cmp[-1] < arr[i]: 
        cmp.append(arr[i])
        d[i] = len(cmp) - 1
        tmp = d[i]
    else:
        d[i] = bisect_left(cmp, arr[i]) 
        cmp[d[i]] = arr[i] 
print(tmp) 

res = []

for i in range(n, 0, -1):
    if d[i] == tmp:
        res.append(arr[i])
        tmp -= 1
        
res.reverse()
print(*res)

BOJ 12015 가장 긴 증가하는 부분 수열 2

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

풀이

from bisect import bisect_left
import sys

input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
stack = [0]

for i in arr:
    if stack[-1] < i:
        stack.append(i)
    else:
        stack[bisect_left(stack, i)] = i

print(len(stack)-1)

BOJ 2805 나무 자르기

문제

상근이는 나무 M미터가 필요하다. 

근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 

정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 

상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 

먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 

높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다.

그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 

따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 

예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 

상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. 

(총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 

이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 

나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다.

높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

예제 입력 1

4 7
20 15 10 17

예제 출력 1

15

예제 입력 2

5 20
4 42 40 26 46

예제 출력 2

36

풀이

import sys

input = sys.stdin.readline
n , m = map(int, input().split())
tree = list(map(int, input().split()))

def cut_tree(arr, start, end):
    res = 0
    while start <= end:
        mid = (start + end) // 2
        total = 0
        
        for x in arr:
            if x > mid:
                total += x - mid
            
        if total < m:
            end = mid - 1
        else:
            res = mid
            start = mid + 1

    return res

print(cut_tree(tree, 0, max(tree)))

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)