그리디 알고리즘 (문제 풀이)

1. 설탕 배달 (백준 2839번)

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

직접 작성한 코드)

 

n=int(input())
count=0
k=n
five= k//5
k=k%5
three=k//3
k=k%3


while True:
    
    if k==0:
        print(five+three)
        break

    elif five<=0:
        if k%3==0:
            three+=k//3
            print(three)
            break
        else:
            print(-1)
            break
    
        
    else :
        
        five-=1
        k=k+5
       
        three+=k//3
        k=k%3

아이디어: 입력받은 수를 5로 최대한 많이 나누고 반복문을 돌면서 5씩 증가시키며 3으로 나누어지는지 확인한다. (3으로 나누는 것 보다 5로 나누는 것이 무조건 큰 경우이기 때문에 적용 가능하다.)

 

5를 나눈 몫이 0이하인데 3으로도 나눠지지 않는다면 -1를 출력한다. 

 

참고 답안) 

 

n = int(input())

if n % 5 == 0:  
    print(n // 5)
else:
    p = 0
    while n > 0:
        n -= 3
        p += 1
        if n % 5 == 0: 
            p += n // 5
            print(p)
            break
        elif n == 1 or n == 2: 
            print(-1)
            break
        elif n == 0: 
            print(p)
            break

 

 

2. ATM(백준 11399번)

https://www.acmicpc.net/problem/11399

11399번: ATM

 

직접 작성한 코드)

 

n=int(input())
array=list(map(int,input().split()))
array.sort()
result=0
count=n

for i in range(n):
    result+=array[i]*count
    count-=1
    
print(result)

 

 

3.  동전 0 (백준 11037번)

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

직접 작성한 코드)

 

n,k=map(int,input().split())
array=[]
result=0
for i in range(n):
    array.append(int(input()))

for j in range(n-1,-1,-1):
   
    result+=k//array[j]
    k=k%array[j]

print(result)

 

 

4. 보물 (백준 1026번)

https://www.acmicpc.net/problem/1026

1026번: 보물

 

직접 작성한 코드)

 

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
result=0
a.sort()
b.sort(reverse=True)

for i in range(n):
    result+=a[i]*b[i]

print(result)

 

5. 잃어버린 괄호 (백준 1541번)

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

직접 작성한 코드)

 

import re
a=input()
numbers=re.findall(r'\d+',a)
calculation=[]
num=[]

for i in a:
    if i=='-' or i=='+':
        calculation.append(i)


for i in range(len(calculation)):
    if calculation[i]=='+':
        numbers[i+1]=int(numbers[i])+int(numbers[i+1])                             
        numbers[i]=0

while 0 in numbers:
    numbers.remove(0)
result=int(numbers[0])*2

for i in numbers:
    result-=int(i)

print(result)

 

아이디어: 결과가 최소가 되려면 뺄셈을 하는 수가 커야한다.

더하기 연산을 우선적으로하고, 이후에 뺄셈을 한다. 

 

참고 답안)

exp = input().split("-")
ans = 0
for i in exp[0].split("+"):
    ans += int(i)

for i in exp[1:]:
    for j in i.split("+"):
        ans -= int(j)

print(ans)