본문 바로가기
반응형

그리디20

(Python/🥇5)백준알고리즘 1548번: 부분 삼각 수열 문제 바로가기 문제: 세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 수열이라고 한다. 이때, i, j, k는 모두 다른 값이다. 수열 A가 주어졌을 때, 이 수열에서 적절히 몇 개의 원소를 빼서 이 수열을 삼각 수열로 만들려고 한다. 삼각 수열의 최대 길이를 구하는 프로그램을 작성하시오. 입력: 첫째 줄에 수열의 크기 N이 주어진다. 둘째 줄에 수열 A에 들어있는 수가 공백을 사이에 두고 주어진다. N은 최대 50이고, A에 들어있는 수는 109보다 작거나 같은 자연수이다. 출력: 첫째 줄에.. 2023. 9. 21.
(Python/🥉2)백준 알고리즘 21313번: 문어 문제 바로가기 문제: 문어에게 여덟개의 팔이 있다는 사실은 잘 알려져 있다. 하지만 문어들이 자신의 팔들을 1번, 2번, 3번, ..., 8번이라고 부른다는 말은 오늘 처음 들었을 것이다! 단, 시계방향으로 오름차순이라던가 하는 규칙은 없다. (물론 그러한 문어도 존재할 수 있다.) 문제에선 편의상 팔 대신 손이라고 부르자. 문어들은 정월 대보름을 맞아 강강술래를 하려고 한다. 각 문어는 양 옆의 서로 다른 두 문어와 손을 맞잡아 원을 만든다. 문어끼리 손을 잡을 때 지켜야 할 예절이 있다. 서로 같은 번호의 손을 잡아야 한다. 한 문어와 둘 이상의 손을 잡을 수 없다. 한 손으로 여러 문어의 손을 잡을 수 없다. 모든 문어들은 예의바르기 때문에 예절을 항상 따른다. 강강술래를 하는 N마리의 문어 중 하.. 2023. 9. 21.
(Python/🥉2)백준 알고리즘 22864번: 피로도 문제 바로가기 문제: 하루에 한 시간 단위로 일을 하거나 일을 쉬어도 된다. 하루에 한 시간 일하면 피로도는 $A$만큼 쌓이고 일은 $B$만큼 처리할 수 있다. 만약에 한 시간을 쉰다면 피로도는 $C$만큼 줄어든다. 단, 피로도가 음수로 내려가면 $0$으로 바뀐다. 당연히 일을 하지 않고 쉬었기 때문에 처리한 일은 없다. 피로도를 최대한 $M$을 넘지 않게 일을 하려고 한다. $M$을 넘기면 일하는데 번아웃이 와서 이미 했던 일들도 다 던져버리고 일을 그만두게 된다. 번아웃이 되지 않도록 일을 할때 하루에 최대 얼마나 일을 할 수 있는지 구해보자. 하루는 24시간이다. 입력: 첫 번째 줄에 네 정수 A B C M이 공백으로 구분되어 주어진다. 맨 처음 피로도는 0이다. 출력: 하루에 번 아웃이 되지 않도.. 2023. 8. 24.
(Python/🥇5)백준알고리즘 2293번: 동전 1 문제 바로가기 문제: n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력: 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력: 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 풀이 : 첫 번째 시도 import sys sys.stdin = open('/Users/song/Desktop/Python/Python/h.tx.. 2023. 7. 23.
(Python/🥈4)백준 알고리즘 2217번: 로프 문제 바로가기 문제: N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 입력: 첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 .. 2023. 7. 6.
(Python/🥈3)백준 알고리즘 17451번: 평행 우주 문제 바로가기 문제: 서기 2XXX년, 지구가 소행성과 충돌할 위기에 처했다! 똑똑한 과학자 키파는 평행 우주를 누비며 지구를 대신할 행성을 찾는 막중한 임무를 맡게 되었다. 우리는 현재 지구(=행성 0)에 있다. 여러 요인을 고려한 결과, 행성 1, 행성 2, …, 행성 (n-1)을 순서대로 확인하고 지구(=행성 n)에 돌아오는 것이 비용상 최적임을 알아냈다. 모든 정수 1 ≤ i < n에 대해, 행성 i은 지구가 아니다. 지구에는 "초고속 걷기 기계"라는, 속도를 원하는 만큼 올릴 수 있는 특수한 장치가 있다. 지구를 벗어나면 속도를 떨어뜨릴 수 있을 뿐 높일 수는 없다. 다음 지역에 가기 위해서는 원칙적으로는 필요한 속도를 정확히 맞춰야 하지만, 다행히도 평행 우주는 일정한 간격을 두고 있기 때문에.. 2023. 7. 5.
반응형

티스토리툴바