728x90

(1) 문제

  • 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
  • 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

(2) 입력

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

 

(3) 출력

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

 

(4) 예제 입력 및 출력

(5) 코드

import sys
coin_kinds, price = map(int, sys.stdin.readline().split())

coin_kinds_list = []
for i in range(coin_kinds):
    coin_kinds_list.append(int(sys.stdin.readline()))

coin_count = 0

for i in range(coin_kinds - 1, -1, -1):
    cur_coin = coin_kinds_list[i]
    if price >= cur_coin:
        cur_coin_count = price // cur_coin
        coin_count += cur_coin_count
        price = price - (cur_coin * cur_coin_count)

print(coin_count)

(6) 실행결과

 

반응형
저작자표시

'BaekJoon Algorithm > Python' 카테고리의 다른 글

[백준알고리즘 - 1037] 약수 (Python)  (0) 2021.03.19
[백준알고리즘 - 11399] ATM (Python)  (0) 2021.03.17
[백준알고리즘 - 1932] 정수 삼각형 (Python)  (0) 2021.03.17
[백준알고리즘 - 1149] RGB거리 (Python)  (0) 2021.03.17
[백준알고리즘 - 9461] 파도반 수열 (Python)  (0) 2021.03.17
728x90

(1) 문제

  • 위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
  • 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
  • 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

(2) 입력

  • 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

(3) 출력

  • 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

(4) 예제 입력 및 출력

(5) 코드

import sys

length = int(sys.stdin.readline())

triangle_list = []

for i in range(length):
    triangle_list.append(list(map(int,input().split())))
    

def bfs(i):
    if i == 0:
        return triangle_list[0][0]
    for j in range(len(triangle_list[i])):
        
        if 0 < j < len(triangle_list[i]) - 1:
            rigth_up = triangle_list[i][j] + triangle_list[i - 1][j]
            left_up = triangle_list[i][j] + triangle_list[i - 1][j - 1]

            if left_up > rigth_up:
                triangle_list[i][j] = left_up
            else:
                triangle_list[i][j] = rigth_up

        elif j == 0:
            rigth_up = triangle_list[i][j] + triangle_list[i - 1][j]
            triangle_list[i][j] = rigth_up

        elif j == len(triangle_list[i]) - 1:
            left_up = triangle_list[i][j] + triangle_list[i - 1][j - 1]
            triangle_list[i][j] = left_up
            

for i in range(length):
    bfs(i)

print(max(triangle_list[length - 1]))

(6) 실행결과

반응형
저작자표시

'BaekJoon Algorithm > Python' 카테고리의 다른 글

[백준알고리즘 - 11399] ATM (Python)  (0) 2021.03.17
[백준알고리즘 - 11047] 동전 0(Python)  (0) 2021.03.17
[백준알고리즘 - 1149] RGB거리 (Python)  (0) 2021.03.17
[백준알고리즘 - 9461] 파도반 수열 (Python)  (0) 2021.03.17
[백준알고리즘 - 2839] 신나는 함수 실행 (Python)  (0) 2021.03.16
728x90

(1) 문제

  • RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
  • 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
    • 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
    • N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
    • i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

(2) 입력

  • 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

(3) 출력

  • 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

(4) 예제 입력 및 출력

(5) 코드

import sys

length = int(sys.stdin.readline())

RGB_price_list = []

for i in range(length):
    RGB_price_list.append(list(map(int, sys.stdin.readline().split())))

def bfs(i):
    for j in range(len(RGB_price_list[i])):
        # if RGB_price_list[i - 1][(j + 1) % 3] < RGB_price_list[i - 1][(j + 2) % 3]:
        #     RGB_price_list[i][j] = RGB_price_list[i - 1][(j + 1) % 3] + RGB_price_list[i][j]
        # else:
        #     RGB_price_list[i][j] = RGB_price_list[i - 1][(j + 2) % 3] + RGB_price_list[i][j]    

        RGB_price_list[i][j] +=  min(RGB_price_list[i - 1][(j + 1) % 3], RGB_price_list[i - 1][(j + 2) % 3])
                     

for i in range(1, length):
    bfs(i)

print(min(RGB_price_list[length - 1]))

(6) 실행결과

반응형
저작자표시

'BaekJoon Algorithm > Python' 카테고리의 다른 글

[백준알고리즘 - 11047] 동전 0(Python)  (0) 2021.03.17
[백준알고리즘 - 1932] 정수 삼각형 (Python)  (0) 2021.03.17
[백준알고리즘 - 9461] 파도반 수열 (Python)  (0) 2021.03.17
[백준알고리즘 - 2839] 신나는 함수 실행 (Python)  (0) 2021.03.16
[백준알고리즘 - 1436] 영화감독 숌 (Python)  (0) 2021.03.16

+ Recent posts

티스토리툴바