Greedy

[Beakjoon] 백준 5911번 Python

Beakjoon 5911, 선물 solved.ac Silver3 Greedy 알고리즘 문제 시흠이는 군대에 가기 전까지 자신과 놀아준 친구 N(1 ≤ N ≤ 1000)명에게 선물을 주려고 한다. 시흠이는 돈을 B(1 ≤ B ≤ 1,000,000,000)원 가지고 있다. i번째 친구가 받고 싶어하는 선물의 가격은 P(i)원이고, 배송비는 S(i)원이다. 즉, 시흠이가 i번째 친구에게 선물을 보내려면 돈이 P(i)+S(i)원 필요하다. 시흠이는 물건 가격을 절반으로 할인받을 수 있는 쿠폰을 하나 가지고 있다. 이 쿠폰을 i번째 친구에게 사용한다면, ⌊P(i)/2⌋+S(i)원만 있으면 선물을 보낼 수 있다. 시흠이가 선물을 최대 몇 명에게 보낼 수 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 B..

[Beakjoon] 백준 1817번 Python

Beakjoon 1817, 짐 챙기는 숌 solved.ac Silver5 Greedy 알고리즘 문제 숌은 짐을 챙겨서 겨울캠프에서 집으로 가려고 한다. 근데 숌은 공부를 많이 하러 캠프에 온 것이기 때문에 책을 엄청나게 많이 가지고 왔다. 숌은 이 책을 방에 탑처럼 쌓아 놨다. 숌은 책을 박스에 차곡차곡 넣어서 택배로 미리 보내려고 한다. 책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수밖에 없다. 각각의 책은 무게가 있다. 그리고 박스는 최대 넣을수 있는 무게가 있다. 숌이 필요한 박스의 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다..

[Beakjoon] 백준 16237번 Python

Beakjoon 16237, 이삿짐센터 solved.ac Silver4 Greedy 알고리즘 문제 알렉스는 이삿짐센터를 운영하고 있다. 오늘 이사해야 하는 집에는 무게가 1kg인 물건이 A개, 2kg인 물건이 B개, 3kg인 물건이 C개, 4kg인 물건이 D개, 5kg인 물건이 E개 있다. 물건을 운반하려면 바구니에 물건을 담아야 하는데, 바구니에는 최대 5kg까지 물건을 담을 수 있다. 알렉스는 모든 물건을 담는데 필요한 바구니 개수를 최소로 하려고 한다. 가방 하나에 담은 물건 무게의 합은 5kg을 넘을 수 없다. 물건의 무게가 주어졌을 때, 모든 물건을 담는데 필요한 바구니 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C, D, E가 주어진다. (0 ≤ A, B, C, ..

[Beakjoon] 백준 5619번 Python

Beakjoon 5619, 세 번째 solved.ac Silver2 Greedy 알고리즘 문제 서로 다른 자연수 n개 a1, a2, ..., an이 주어진다. 이때, a1, ... an에서 2개를 선택해서 붙여서 새로운 수를 만들 수 있다. 이때, 세 번째로 작은 수를 구하는 프로그램을 작성하시오. 예를 들어, 3과 4를 합치면 34나 43이 된다. 또, a1 = 1, a4 = 11을 합쳐서 111을 만든 경우에, a1a4와 a4a1은 다른 수이다. 입력 첫째 줄에 수의 개수 n(3 ≤ n ≤ 108)이 주어진다. 다음 줄부터 한 줄에 하나씩 ai가 주어진다. (1 ≤ ai ≤ 10000) 출력 세 번째로 작은 수를 출력한다. Sulution n = int(input()) data = [] for _ i..

[Beakjoon] 백준 1902번 Python

Beakjoon 1902, 배 solved.ac Gold5 Greedy 알고리즘 문제 지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다. 각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다...

[Beakjoon] 백준 23351번 Python

Beakjoon 23351, 물 주기 solved.ac Silver3 Greedy 알고리즘 문제 랑이 집사는 고양이들이 좋아한다는 캣닢을 직접 재배하려고 한다. 일직선으로 놓여진 N개의 화분에 캣닢이 하나씩 심어져 있다. 각 화분은 초기에 K만큼의 수분을 머금고 있고, 매일 아래와 같은 일이 순서대로 일어난다. 랑이 집사가 연속된 A개의 화분에 물을 준다. 이 때 물을 준 화분의 수분은 B만큼씩 증가한다. 모든 화분의 수분이 1씩 감소한다. 수분이 0이 된 화분에 있는 캣닢은 죽는다. 모든 캣닢이 살아 있는 기간이 최대한 길어지도록 물을 줄 때, 첫 캣닢이 죽는 날짜를 출력하는 프로그램을 작성하시오. 첫 날은 1일이다. 입력 첫째 줄에 자연수 N, K, A, B가 공백을 사이에 두고 주어진다. (2≤N≤..

[Beakjoon] 백준 16471번 Python

Beakjoon 16471, 작은 수 내기 solved.ac Silver4 Greedy 알고리즘 문제 여자친구와 함께 보드게임카페에 간 주언이는, 여러 보드게임을 하며 데이트를 즐겼다. 3시간 커플세트로 결제를 하려던 순간, 주언이는 가격표 옆에 쓰여 있는 새로운 이벤트를 보았다. 바로 “사장님과의 게임에서 이기면 무료, 지거나 비기면 5000원 추가 지불” 이벤트였다. 보드게임에 자신이 있는 주언이는 사장님에게 게임 룰을 물어보았고, 그 룰은 다음과 같았다. 각자 N장의 카드를 받는다. (N은 홀수다) 각자 카드를 1장씩 골라서 카드에 적힌 수의 크기를 비교한다. (각 카드에 적힌 수는 0이상, 100,000이하의 정수다) 더 작은 수가 적힌 카드를 낸 사람이 1점을 얻고, 승부에 사용된 카드는 버린다..

[Beakjoon] 백준 9237번 Python

Beakjoon 9237, 이장님 초대 solved.ac Silver5 Greedy알고리즘 문제 농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다. 상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다. 상근이는 나무를 심는 순서를 신중하게 골라 이장님을 최대한 빨리 초대하려고 한다. 이장님을 며칠에 초대할 수 있을까? 입력 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 ..

[Beakjoon] 백준 1026번 Python

Beakjoon 1026, 보물 solved.ac Silver4 Greedy 알고리즘 문제 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0] × B[0] + ... + A[N-1] × B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다. S의 최솟값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 10..

[Beakjoon] 백준 1789번 Python

Beakjoon 1789, 수들의 합 solved.ac Silver5 Greedy 알고리즘 문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 출력 첫째 줄에 자연수 N의 최댓값을 출력한다. Solution n = int(input()) count = 0 cnt = 0 if n == 1: print(1) exit() for i in range(0,n): count += i + 1 if count > n: print(cnt) break cnt += 1 풀이 1 + 2 + 3 + ... + N을 반복합니다. cnt는 더하는 횟수이며 이는 서로 다른 수가 됩니다. 그리고 count는 ..