[Python3] 백준 기본 문제 풀기 | 백준 14916 : 거스름돈

 

#1. 백준2501 : 약수 구하기(브론즈 3티어)

입력 : 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

출력 : 첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 0을 출력하시오.

# n,k 공백으로 입력받기
n,k = map(int,input().split())
result = []

# 1부터 n까지 n의 약수 구하여, result에 넣어주기
for i in range(1, n+1):
    if n % i == 0:
        result.append(i)

# result를 오름차순 정렬
result.sort()

# k번째 약수 구하기
if len(result) < k:
    print(0)
else:
    print(result[k-1])

 

 

#2. 백준3460 : 이진수(브론즈 3티어)

입력 : 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. (1 ≤ T ≤ 10, 1 ≤ n ≤ 106)

출력 : 각 테스트 케이스에 대해서, 1의 위치를 공백으로 구분해서 줄 하나에 출력한다. 위치가 낮은 것부터 출력한다.

 

#테스트 케이스
T = int(input())

# 양의 정수 n 입력받기 | bin은 10진수를 2진수로 바꿔주는 함수
# Ob011110 형식으로 나오는데, Ob를 제외하기 위해 [2:]
for _ in range(T):
    n = bin(int(input()))[2:]
    for i in range(len(n)):
        # 이진수의 값을 역순으로 출력해야 하기 때문에, 역순으로 문자열을 찾음
        if n[i-1] == '1':
            print(i, end= " ")

 

#3. 백준10818 : 최소, 최대(브론즈 3티어)

입력 : 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.

출력 :  첫째 줄에 주어진 정수 N개의 최솟값과 최댓값을 공백으로 구분해 출력한다.

# N의 갯수 입력받기
T = int(input())

# N을 리스트에 저장
n = list(map(int,input().split()))
# 리스트 중에 최소, 최대값 구하기
min_value = min(n)
max_value = max(n)

print(min_value, max_value)

 

#4. 백준2460 : 지능형 기차2(브론즈 3티어)

입력 : 각 역에서 내린 사람 수와 탄 사람 수가 빈칸을 사이에 두고 첫째 줄부터 열 번째 줄까지 역 순서대로 한 줄에 하나씩 주어진다. 

출력 : 첫째 줄에 최대 사람 수를 출력한다.  

 

#방법 1

# 내린 사람 수와 탄 사람 수를 리스트로 정의
down_list = []
up_list = []

for i in range(10):
    down, up = map(int,input().split())
    down_list.append(down)
    up_list.append(up)

# 역 별로 탄 사람 수 합계를 구함
sum_up = 0
sum_uplist = []
for i in up_list:
    sum_up += i
    sum_uplist.append(sum_up)

# 역 별로 내린 사람 수 합계를 구함
sum_down = 0
sum_downlist = []
for i in down_list:
    sum_down += i
    sum_downlist.append(sum_down)

# 역 별로 (전체 탄 사람 수) - (전체 내린 사람 수)를 구해서 최댓값을 구함
result = 0
for i in range(10):
    sum = sum_uplist[i] - sum_downlist[i]
    result = max(result, sum)

print(result)

 

#방법2

# 정거장당 사람 수 리스트로 저장
num = 0
result = []

for i in range(10):
    down, up = list(map(int,input().split()))
    num = num - down + up #내리고 타기
    result.append(num)

# 가장 사람이 많았던 사람 수대로 내림차순 정렬
result.sort(reverse=True)
print(result[0])

 

 

#백준 14916 : 거스름돈(실버5 티어)

입력 : 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력 : 거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

 

# 방법1 : 다이나믹 프로그래밍

n = int(input())

# 화폐 단위 정보
array = [2,5]

# dp 테이블 초기화
d = [100001] * (n+1)

# 0원을 만들기 위한 동전 개수는 0개
d[0] = 0

# 각 동전 단위(2원, 5원)에 대해 dp 테이블 갱신
for coin in [2,5]:
    for i in range(coin, n + 1):
        if d[i - coin] != 100001: #불가능한 경우를 제외
            d[i] = min(d[i], d[i - coin] + 1)

#계산된 결과 출력
if d[n] == 100001:
    print(-1)
else:
    print(d[n])

 

# 방법2 : 다이나믹 프로그래밍

n = int(input())

# dp테이블 초기화
dp = [-1] * (n+8)

# 최소 동전 개수 설정
dp[2] = 1 #2원 : 2*1
dp[4] = 2 #4원 : 2*2
dp[5] = 1 #5원 : 5*1
dp[6] = 3 #6원 : 2*3
dp[7] = 2 #7원 : 5*1 + 2*1
dp[8] = 4 #8원 : 2*4

# 9원부터 n원까지의 최소 동전 개수 출력
for i in range(9, n+1):
    dp[i] = min(dp[i-2], dp[i-5]) + 1
print(dp[n])

 

#방법3 : 수학적 접근

n = int(input())

count = 0
i = 0

while True:
    if n % 5 == 0: # 5의 배수
        count += n //5
        break
    else:
        n -= 2 #2원씩 빼면서 5의 배수가 나오도록
        count += 1

    if n < 0: # 거슬러줄 수 없는 경우
        break
if n < 0:
    print(-1)
else:
    print(count)

 

#방법4 : 수학적접근

n = int(input())

#최소 동전 개수 초기화
min_coins = -1

# 5원짜리 동전 개수를 최대한 많이 사용하면서 확인
for coin in range(n//5, -1, -1):
    remainder = n - (coin * 5)
    if remainder % 2 == 0:
        min_coins = coin + (remainder // 2)
        break

print(min_coins)

 

#백준 5585 : 거스름돈

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

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

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

n = int(input())

coin_types = [500,100,50,10,5,1]
change = 1000 - n
result = 0


for coin in coin_types:
    result += change // coin
    change %= coin

print(result)