IT-garden

문제

어느 날, 미르코는 우연히 길거리에서 양수 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

ord()함수는 특정한 문자를 아스키 코드 값으로 바꿔줍니다.

# 출력>>65
print(ord('A'))

# 출력>>97
print(ord('a'))

# 출력>>49
print(ord('1'))

chr()함수는 아스키 코드 값을 문자로 변환해줍니다.

# 출력>>A
print(chr(65))

# 출력>>a
print(chr(97))

# 출력>>1
print(chr(49))

sum()함수는 요소를 모두 더한 값을 제공합니다.

a=[1,3,5]

# 결과>>9
print(sum(a))

max()함수는 요소 중 가장 큰 값을 반환합니다.

a=[1,3,5]
b=['a','b','c']

# 결과>>5
print(max(a))

print(ord('a')) #결과>>97
print(ord('b')) #결과>>98
print(ord('c')) #결과>>99

# 결과>>c
print(max(b))

문자열은 코드값으로 최대값을 반환합니다.

min()함수는 요소 중 가장 작은 값을 반환합니다.

a=[1,3,5]
b=['a','b','c']

# 결과>>1
print(min(a))

print(ord('a')) #결과>>97
print(ord('b')) #결과>>98
print(ord('c')) #결과>>99

# 결과>>a
print(min(b))

문자열은 코드값으로 최소값을 반환합니다.

문제

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

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

동전 교환

정답

n,k=input().split(' ')
n=int(n)
k=int(k)
a=[]
b=0

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

a.sort()

for j in range(n-1,-1,-1):

    c=a[j]
    if k // c >= 1:

        b=b + k // c
        k=k - c * (k // c)
        
    if k <= 0:
        break
    
print(b)

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