코딩테스트 스터디 1주차-Greedy_1

백준 13305 주유소

현재 min(가격의 최솟값)보다 다음 주유소의 가격이 더 낮으면 min 최신화,
min * dist(거리) 누적합 계산

n =  int(input())
dist = list(map(int,input().split()))
oil = list(map(int,input().split()))

whattochoose = []

for i in range(len(oil)):
    whattochoose.append(0)

min = oil[0]
whattochoose[0] = 1
for i in range(len(oil)):
    if oil[i] < min:
        whattochoose[i] = 1
        min = oil[i]

price = oil[0]
result = 0
for i in range(len(dist)):
    if whattochoose[i] == 1:
        price = oil[i]
    result += price * dist[i]
print(result)

2785 체인

한번 걸어 잠글 때마다 맨 앞 리스트의 요소에서 1을 뺄 거임
만약 그 요소가 0이 된다면 다음 요소에서 빼게 됨

체인의 각 간격을 잠글 때마다 1회 열고 닫음

이때 잠그는 시행을 체인이 적은 것부터 시행을 함

1 3 3
이 경우 첫 번째 체인을 2,3번째 체인을 잠그는데에 사용했으니 0이 됨
0 3 3

이 경우에는

이렇게 한번 잠그고

3개짜리에서 하나 끊어서 잠가야함

이 시행이 끝나면 리스트는
1 3 3 3에서
0 2 3 3이 됨

--> 시행이 끝난 후의 0이 아닌 요소의 길이 - 1이 답이 됨

n = int(input())
li = list(map(int,input().split()))
li.sort()
k = 0
result = 0
for i in reversed(range(len(li)-1)):
    if li[k] == 0:
        k += 1
    if li[i] > 0:
        li[k] -= 1
        result += 1
print(result)
    

숫자놀이

주어진 값을 나누는 값 중 가장 큰 값(9이하의 수에서)을 리스트에 삽입, 리스트의 원소의 개수를 반환

만약 2,3,5,7로 나눠지지 않으면 -1 반환

k = int(input())
for m in range(k):
    n = int(input())
    if n == 1:
        print(1)
        continue
    li = []


    boo = True

    while True:
        for i in reversed(range(2,10)):
            if n%i == 0:
                n /= i
                li.append(i)
                break
        if n == 1:
            break
        
        if (n % 2 != 0 ) & (n % 3 != 0 ) & (n % 5 != 0 ) & (n % 7 != 0 ):
            boo = False
            break
    if boo == False:
        print(-1)
    else:
        print(len(li))