Jinho Tech

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

-> 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

우선 입력을 리스트에 저장하고 오름차순 정렬해준다.

그 후 첫 번째 값부터 마지막 값까지 누적 값을 순서대로 더해주면 된다.

EX) 입력: 3, 1, 4, 3, 2

리스트로 만든 후 정렬 -> [1, 2, 3, 3, 4]

누적 값을 순서대로 더함 -> 1 + (1+2) + (1+2+3) + (1+2+3+3) + (1+2+3+3+4) = 1+3+6+9+13 = 32

답: 32

N = int(input())
li = sorted(list(map(int, input().split())))
ans = 0
for i in range(N):
    ans += sum(li[:i+1])
print(ans)

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

EX) K = 4200, 입력: 1 5 10 50 100 500 1000 5000 10000 50000

ans = 0

1) 4200 - 1000*4 = 200 -> ans = 0 + 4 = 4

2) 200 - 100*2 = 0 -> ans = 4 + 2 = 6 -> 6 출력

N, K = map(int, input().split())
li = sorted([int(input()) for _ in range(N)], reverse=True)
cnt = 0
for c in li:
    if c <= K:
        cnt += K//c
        K %= c
    if K == 0:
        break
print(cnt)

5킬로그램짜리를 최대한 많이 배달하는 게 포인트다.

입력 N이 5로 나누어질 때까지 3을 계속 빼고 이 과정을 몇 번 반복했는지 새면 된다.

3을 계속 빼도 끝까지 5로 나누었을 때 0이 안된다면 N킬로그램을 정확하게 만들 수 없는 경우이다.

EX) N = 18

(18-0)%5 != 0 -> i = 1

(18-3)%5 == 0 -> 정답 = 15//5 + i = 3 + 1 = 4

n = int(input())
i = ok = 0
while(i < n/3+1):
    if (n - 3*i) % 5 == 0:
        ok = 1
        break
    i += 1
print((n-3*i)//5+i) if ok else print(-1)

k개의 로프를 사용할 때 들어 올릴 수 있는 중량은

버틸 수 있는 중량이 제일 작은 로프의 최대 중량 * k라는 점이 핵심이다. 

EX) 15, 10 로프 2개를 사용할 경우

최대 10 * 2 = 20인데 이유는 15가 10보다 큰 중량을 버틸 수 있더라도 로프에 걸리는 중량은 똑같기 때문에 10을 기준으로 최대 중량이 정해지기 때문이다.

N = int(input())
li = sorted([int(input()) for _ in range(N)], reverse=True)
ans = 0
for i in range(N):
    ans = max(ans, li[i]*(i+1))
print(ans)

그리디 알고리즘 문제이다. 정렬을 사용하면 쉽게 풀 수 있다!

lambda를 사용해 끝나는 시간과 시작하는 시간 순으로 두 번 정렬해주는 게 핵심이다. 

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

처음으로 '-'가 나오는 순간부터 그 뒤에 있는 숫자들은 무조건 빼야 된다는 것을 이해하면 간단하게 풀 수 있다!

EX) 입력이 "55+10-50+40-20+20"이면 

li = ["55+10", "50+40", "20+20"]가 되는데 처음 요소인 "55+10"의 합에 뒤에 있는 모든 요소들의 합을 빼주면 된다. 

-> (55+10) - (50+40) - (20+20) = 65 - 90 - 40 = -65

li = input().split('-')
ans = sum(map(int, li[0].split('+')))
for s in li[1:]:
    ans -= sum(map(int, s.split('+')))
print(ans)