IT-garden

문제

Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

정답

n,m=input().split(' ')
n=int(n)
m=int(m)

c=list()
d=list()

for i in range(m):
    a,b=input().split(' ')
    c.append(int(a))
    d.append(int(b))

e=min(c)
f=min(d)

if e < f*6:
    if e < (n%6)*f:
        print((n//6) * e + e)
    else:
        print((n//6) * e + (n%6) * f)

elif e >= f*6:
    print(n*f)

각 브랜드의 패키지 가격은 리스트 c에 저장하고 낱개의 가격은 리스트 d에 저장합니다.

각 리스트의 최소값을 e와 f에 저장합니다.

패키지에는 기타줄이 6개이기 때문에 패키지와 낱개의 가격을 6개를 기준으로 비교합니다.

패키지가 더 저렴한 경우 패키지를 사고 남는 낱개의 개수와 패키지의 가격을 비교해 6개 미만의 낱개를 각각 낱개로 구매하는게 저렴한지 패키지 하나를 구매하는게 저렴한지 비교합니다.

패키지가 저렴한 경우 (n//6) * e + e

낱개가 저렴한 경우 (n//6) * e + (n%6) * f

낱개 6개의 가격이 패키지와 같거나 더 저렴한 경우 n*f 로 계산합니다. 

백준 알고리즘 1049번 : https://www.acmicpc.net/problem/1049

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 길이가 최대 50인 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.

출력

첫째 줄에 정답을 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

정답

a=input().split('-')
b=0

for i in a[0].split('+'):
    b=b+int(i)

for j in range(1,len(a)):
    for k in a[j].split('+'):
        b=b-int(k)
    
print(b)

* 식의 값을 최소로 만들기 위해서는 -뒤의 값을 크게 해서 -를 해줘야 합니다.

그래서 식을 입력받을때 -를 기준으로 나눠줍니다.

백준 알고리즘 1541번 : https://www.acmicpc.net/problem/1541

문제

백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)

백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다.

백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다.

여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다.

입력

첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N),

출력

만들 수 있는 팀의 최대 개수을 출력하면 된다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

정답

n,m,k=input().split(' ')

n=int(n)
m=int(m)
k=int(k)

nn= n // 2
a= n % 2

c=0 
b=0 

if nn > m:
    c=m
    b=(nn-m)*2+a
elif nn == m:
    c=nn
    b=a
elif nn < m:
    c=nn
    b=m-nn+a

while True:
    if b >= k:
        break
    
    else:
        b=b+3
        c=c-1

print(c)

여학생은 2명이 필요하니까 몫을 nn에 저장하고 나머지는 a에 저장합니다.

c는 만들수 있는 팀의 수를 세기 위한 변수입니다.
b는 나머지로 k랑 비교하기 위한 변수입니다.

if : nn이 m보다 크면 nn-m하고 *2를 해줍니다.

처음 여학생은 ÷2를 해줬으니 다시 곱해주어야 하기 때문입니다.
그 후 나머지 a를 더해줍니다.

elif : nn과 m이 같으면 c=nn이나 c=m입니다.

elif : nn이 m보다 작으면 m-nn 하고 a를 더해줍니다.

while문 무한루프를 통해 k가 충족되었는지 확인합니다.

b>=k이면 무한루프를 나가 c 출력합니다.
b<k이면 b에 3 더하고 (2명의 여학생, 1명의 남학생) c에서 1 을 빼줍니다. (한 팀을 없애고 인턴쉽 학생으로 추가!)

백준 알고리즘 2875번 : https://www.acmicpc.net/problem/2875

문제

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

입력

N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

출력

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

정수론

정답

n=input()
a=[]

for i in range(len(n)):
    a.append(int(n[i]))

a.sort(reverse=True)

b=0
c=''

if a[-1] == 0:
    a.pop()

    for j in range(len(a)):
        b= b+a[j]
        
    if b % 3 == 0:
        a=list(map(str,a))

        for k in range(len(a)):
            c=c+ a[k]
              
        print(int(c) * 10)      
        
    else:
        print(-1)

else:
    print(-1)

*3의 배수의 특징은 각 자릿수를 모두 더하고 3으로 나눴을 때 나눠 떨어지면 3의 배수라는 점입니다.

30 → 3+0=3 , 3 ÷ 3=1

102 → 1+0+2, 3 ÷ 3=1

2931 → 2+9+3+1=15, 15 ÷ 3=5

80875542  → 8+0+8+7+5+5+4+2=39, 39 ÷ 3=13

이를 이용해 30의 배수가 되는 수를 구했습니다.

30의 배수이려면 3의 배수이면서 숫자 0이 들어가 있는지 확인했습니다.

for문을 통해 양수 n을 한자리씩 구분해 a라는 리스트에 넣고 내림차순으로 정렬해줍니다.

if문을 통해 리스트 a의 마지막 수( a[-1])가 0인지 확인했습니다.
마지막 수를 확인한 이유는 리스트 a를 내림차순으로 정렬했기 때문입니다.

리스트 a에 숫자 0이 있다면 이를 지우고 리스트의 값들을 b에 더했습니다.

b의 값을 3으로 나눴을 때 나눠 떨어지는지 확인하여 이에 속하면 리스트 a의 값들을 int형에서 str형으로 바꿔주었습니다.

그리고 리스트 a의 값을 str형으로 c에 더해주었습니다.

c를 int형으로 바꾸고 아까 제외한 10을 곱해주어 결과를 출력해주었습니다.

30의 배수가 되는 가장 큰 수를 만들어야 해서 리스트 a를 내림차순으로 정렬하고 3의 배수의 특징을 이용해
답을 구했습니다. (어차피 3의 배수라면 각 숫자의 자리는 상관없으니까 가장 큰순서로 출력하기 위해 정렬!!)

백준 알고리즘 10610번 : https://www.acmicpc.net/problem/10610

문제

N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

정답

n=input()
n=int(n)
a=[]
b=[]

for i in range(n):
    a.append(int(input()))

a.sort(reverse=True)

for j in range(n):
    b.append(a[j] * (j + 1))
    
print(max(b))

* 예시를 통해보면

15로프에서는 15 무게 가능, 10로프에서는 10 무게 불가능  : 15*1=15

15로프에서는 10 무게 가능, 10로프에서는 10 무게 가능     : 10*2=20

a.sort(reverse=True)를 이용해 내림차순으로 정렬합니다.

a의 자리의 값 * 위치의 수를 계산해 리스트를 만들어 리스트에서 최대값을 출력합니다.

백준 알고리즘 2217번 : https://www.acmicpc.net/problem/2217

문제

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다.

입력

입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.

출력

제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

구현

정답

a=input()
a=int(a)

m=[500,100,50,10,5,1]
n=1000-a
s=0

for i in range(len(m)):

    b=m[i]
    c=n//b
    
    if c >= 1:
        s=s + c
        n=n - b * c
    if n==0:
        break

print(s)

백준 알고리즘 5585번 : https://www.acmicpc.net/problem/5585