IT-garden

문제

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

• 전체를 뒤집으면 1110011이 된다.
• 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

정답

s=input()   
a=0
b=0

if s[0] == '0':
    a=1
else:
    b=1

for i in range(1,len(s)):
    if s[i] != s[i-1]:
        if s[i]== '0':
            a+=1
        else:
            b+=1

if a>=b:
    print(b)
else:
    print(a)

a는 0으로 바뀌는 횟수, b는 1로 바꾸는 횟수를 계산하고 이 중 작은 수를 출력합니다.

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

문제

백준대학교에서는 대회에 나갈 때 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

문제

준규가 가지고 있는 동전은 총 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