Jinho Tech

python3에는 오버플로우가 없어서 엄청 큰 수가 들어와도 따로 처리해줄 필요가 없다.

그냥 그대로 출력해주면 된다.

n, m = map(int, input().split())
print(n//m)
print(n%m)

단순하게 A랑 B를 비교하면서 개수를 새면 시간 초과가 나와서 이분 탐색을 사용했다.

이분 탐색을 사용해 B에서 A의 한 요소(a) 보다 작은 수들 중에 제일 큰 수의 위치(인덱스)를 찾는 것이 핵심이다.

EX) A = [2, 7, 13], B = [11, 103, 215, 290] 일 때

cnt = 0

A[0] = 2 -> B에는 2보다 작은 수가 없음 -> res = -1 -> cnt += (-1 + 1) -> cnt = 0

A[1] = 7 -> B에는 7보다 작은 수가 없음 -> res = -1 -> cnt += (-1 + 1) -> cnt = 0

A[2] = 13 -> B에서 13보다 작은 수는 2 인덱스는 0 -> res = 0 -> cnt += (0 + 1) -> cnt = 1

결과: 1

def binary_search(li, a):
    s, e = 0, len(li)-1
    res = -1
    while s <= e:
        m = (s + e) // 2
        if li[m] < a:
            res = m
            s = m + 1
        else:
            e = m - 1
    return res
    
    
for _ in range(int(input())):
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    cnt = 0
    for a in A:
        cnt += (binary_search(B, a) + 1)
    print(cnt)

bisect 라이브러리를 활용하면 훨씬 짧고 빠르게 해결할 수 있다.

import bisect

for _ in range(int(input())):
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    cnt = 0
    for a in A:
        cnt += (bisect.bisect(B, a-1))
    print(cnt)

더하는 수들이 long long 타입보다 크기 때문에 c 같은 언어로 풀려면 배열을 사용해서 더해줘야 하는데

python은 그런 게 없어서 그냥 더해주면 된다.

print(sum(map(int, input().split())))

2805번 나무 자르기와 거의 똑같은 문제이다.

이제 이런 종류의 이분 탐색 문제는 익숙해진 건지 3분 만에 풀었다!

def binarySearch(li, M):
    s, e = 1, max(li)
    ans = 0
    while s <= e:
        m = (s + e) // 2
        t = 0
        for n in li:
            if n > m:
                t += m
            else:
                t += n
        if t <= M:
            s = m + 1
            ans = m
        else:
            e = m - 1
    return ans


N = int(input())
li = list(map(int, input().split()))
M = int(input())
print(binarySearch(li, M))

이분 탐색을 활용해서 풀어야 되는 문제이다.

절단기의 높이가 m일 때 가져갈 수 있는 나무의 길이가 M 이상이면 절단기의 높이를 올려도 되므로 s = m + 1

작다면 높이를 내려야 하므로 e = m - 1을 해준다.

def binarySearch(li, M):
    s, e = 1, max(li)
    ans = 0
    while s <= e:
        m = (s + e) // 2
        t = 0
        for n in li:
            if n > m:
                t += n-m    
        if t >= M:
            s = m + 1
            ans = m
        else:
            e = m - 1
    return ans
    
    
N, M = map(int, input().split())
li = sorted(list(map(int, input().split())))
print(binarySearch(li, M))

아주 기본적인 이분 탐색 문제이다!

def binarySearch(li, n):
    s, e = 0, len(li)-1
    while s <= e:
        m = (s + e) // 2
        if li[m] == n:
            return 1
        elif li[m] <= n:
            s = m + 1
        else:
            e = m - 1
    return 0


_ = int(input())
li = sorted(list(map(int, input().split())))
N = int(input())
for n in list(map(int, input().split())):
    print(binarySearch(li, n))

기름 가격의 최솟값을 잘 사용하면 쉽게 풀 수 있다.

-> res += 현재까지 확인한 기름 가격들의 최솟값 * 현재 가야 되는 거리 

EX) dis = [2, 3, 1], oil = [5, 2, 4, 1]

처음엔 기름 가격의 최솟값이 5이므로 5*2만큼의 비용이 들지만,

그 이후엔 최솟값이 2이므로 2*3 

마지막에도 최솟값이 2이므로 2*1 만큼의 비용이 들게 된다. 다 더하면 5*2 + 2*3 + 2*1 = 18이다.

N = int(input())
dis = list(map(int, input().split()))
oil = list(map(int, input().split()))
m = 10000000001
res = 0

for i in range(N-1):
    if oil[i] < m:
        m = oil[i]
    res += dis[i]*m
print(res)

간단한 수학 문제이다. min(V%P, L) 부분이 핵심인 것 같다.

i = 1
while 1:
    L, P, V = map(int, input().split())
    if L == 0 and P == 0 and V == 0:
        break
    res = L*(V//P) + min(V%P, L)
    print("Case {0}: {1}".format(i, res))
    i += 1

서류심사 성적을 기준으로 오름차순 정렬 

-> 면접 성적의 최솟값(확인한 것 중 제일 높은 순위)이 몇 번 업데이트되는지 확인

for _ in range(int(input())):
    N = int(input())
    li = [list(map(int, input().split())) for i in range(N)]
    li.sort(key=lambda x:x[0])
    m, cnt = 100001, 0
    for i in range(N):
        if li[i][1] < m:
            m = li[i][1]
            cnt += 1
    print(cnt)

위의 코드도 맞긴 하는데 시간 초과가 걸린다. std.readline을 사용해서 해결했다.

from sys import stdin

for _ in range(int(stdin.readline())):
    N = int(stdin.readline())
    li = [list(map(int, stdin.readline().split())) for i in range(N)]
    li.sort(key=lambda x:x[0])
    m, cnt = 100001, 0
    for i in range(N):
        if li[i][1] < m:
            m = li[i][1]
            cnt += 1
    print(cnt)

마지막 레벨의 점수부터 확인을 하는데,

만약 뒷 단계보다 앞 단계의 점수가 더 크다면 앞 단계의 점수를 뒷 단계의 점수보다 1 작게 되도록 빼주면 된다.

N = int(input())
li = [int(input()) for _ in range(N)][::-1]
ans = 0
for i in range(N-1):
    if li[i] <= li[i+1]:
        m = li[i+1] - li[i] + 1
        ans += m
        li[i+1] -= m 
print(ans)

입력으로 받은 문자열이 0에서 1로, 1에서 0으로 총 몇 번 바뀌는지를 구하면 쉽게 풀 수 있다.

홀수번 바뀔 경우 -> cnt//2 + 1

짝수번 바뀔 경우 -> cnt//2

s = input()
cnt = 0
for i in range(len(s)-1):
    if s[i] != s[i+1]:
        cnt += 1
print(cnt//2 + 1 if cnt % 2 else cnt//2)

11047번 동전 0과 거의 똑같은 문제이다.

거스름돈보다 싼 동전 중에서 제일 큰 것부터 순서대로 꽉꽉 채운다는 느낌으로 풀면 된다.

change = 1000 - int(input())
cnt = 0
for c in [500, 100, 50, 10, 5, 1]:
    if c <= change:
        cnt += change//c
        change %= c
    if change == 0:
        break
print(cnt)

그리디 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

정렬을 사용하면 쉽게 풀 수 있는 그리드 알고리즘 문제들이 되게 많다.

백준 알고리즘 문제 풀이)

jinho-study.tistory.com/62

jinho-study.tistory.com/111

jinho-study.tistory.com/198

jinho-study.tistory.com/195

jinho-study.tistory.com/301

jinho-study.tistory.com/39

jinho-study.tistory.com/75

jinho-study.tistory.com/36

jinho-study.tistory.com/302

jinho-study.tistory.com/303

jinho-study.tistory.com/304

jinho-study.tistory.com/305

jinho-study.tistory.com/306

https://jinho-study.tistory.com/1101

split 함수를 사용해주면 쉽게 풀린다.

for _ in range(int(input())):
    print(sum(map(int , input().split(','))))

이분 탐색 문제이다. 2110번 공유기 설치와 비슷한 문제다. 

def count(li, m):
    cnt = 0
    for n in li:
        cnt += (n // m)
    return cnt
            
def binarySearch(li, K):
    s, e = 1, max(li)
    while s <= e:
        m = (s + e) // 2
        if count(li, m) >= K:
            ans = m
            s = m + 1
        else:
            e = m - 1
    return ans
    
    
N, K = map(int, input().split())
li = sorted([int(input()) for _ in range(N)])

print(binarySearch(li, K))