본문 바로가기

GREEDY28

[Greedy/그리디] 백준 14487 욱제는 효도쟁이야!! - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 14487번: 욱제는 효도쟁이야!! 욱제는 KOI를 망친 기념으로 부모님과 함께 코드게이트 섬으로 여행을 떠났다. 코드게이트 섬에는 오징어로 유명한 준오마을(심술쟁이 해커 임준오 아님), 밥으로 유명한 재훈마을, 영중마을 등 www.acmicpc.net 2. 문제 풀이 원형으로 이어진 관광지 간 도로의 이동비용이 주어집니다. 이들을 순회하는 데에 필요한 최소 비용을 계산해야 합니다. 원형으로 순회할 때, 한 곳은 지나지 않아도 됩니다. 즉, 제일 비싼 교통비가 드는 경로만 제외하고 순회합니다. 3. 코드 import sys input = sys.stdin.readline # 입력 n = int(input()) # 마을의 수 town = list(map(in.. 2022. 11. 15.
[그리디/Greedy] 백준 1758 알바생 강호 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 2. 문제 풀이 팁 + (1 - 순서) 최대한 많은 팁을 얻어야 합니다. 순서가 늦어질수록 팁이 낮아지며, 음수가 되면 아예 받지 못합니다. 2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 경주마들을 자세히 보면, 양쪽 시야를 차단하는 안대를 끼고 있습.. 2022. 11. 6.
[그리디/Greedy] 백준 1105 팔 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1105번: 팔 첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 문제 풀이 L과 R 사이에 있는 수 중에서 8이 가장 적게 들어간 수를 찾아, 8의 개수를 출력하는 문제입니다. 1) L과 R의 자릿수가 다른 경우: 0개 2) L과 R의 자릿수가 동일한 경우: 왼쪽 끝부터 동일한 자릿대 + 8인 개수를 파악 (단, 동일 숫자가 아니면 break) 1의 경우, 자릿수가 넘어갈 때 9, 99, 999와 같이 8이 0인 수가 나오므로 0개입니다. 2의 경우는, 고정된 8의 개수를 찾아야 합니다. 앞 자리가 동.. 2022. 10. 6.
[그리디/Greedy] 백준 14469 소가 길을 건너간 이유 3 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 14469번: 소가 길을 건너간 이유 3 이웃 농장의 소가 길을 마구잡이로 건너는 것에 진절머리가 난 존은 극단의 결정을 내린다. 농장 둘레에 매우 큰 울타리를 짓는 것이다. 이렇게 하면 근처 농장 출신의 소가 들어올 일이 거의 없 www.acmicpc.net 2. 문제 풀이 소들의 도착시간, 검문에 필요한 시간이 주어집니다. 검문은 1마리씩 가능하며, 모든 소들을 입장시키는 데에 필요한 최소 시간을 구해야 합니다. 2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 경주마들을 자세히 보면, 양쪽 시야를 차단하는 안.. 2022. 9. 30.
[그리디/Greedy] 백준 11034 캥거루 세마리 2 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11034번: 캥거루 세마리2 여러개의 테스트 케이스로 이루어져 있으며, 세 캥거루의 초기 위치 A, B, C가 주어진다. (0 < A < B < C < 100) www.acmicpc.net 2. 문제 풀이 캥거루 세 마리의 위치가 주어집니다. 바깥쪽에 있는 캥거루만, 둘 사이로 점프해서 들어갈 수 있습니다. 최대 점프를 몇 번 할 수 있는지를 구해야 합니다. 둘 사이가 넓은 쪽으로 점프해서, 한 칸씩 이동하면 됩니다. 굳이 중간으로 점프해서 간격을 줄일 필요가 없습니다. 3. 코드 import sys input = sys.stdin.readline while True: try: # 입력 A, B, C = map(int, input().split()) # .. 2022. 9. 27.
[Greedy/그리디] 백준 16435 스네이크버드 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net 2. 문제 풀이 스네이크버드의 길이와 과일들의 높이가 주어집니다. 스네이크버드가 과일을 1개 먹을 때마다 1씩 길이가 늘어나며, 자신의 길이보다 낮거나 같은 과일들은 먹을 수 있습니다. 스네이크버드가 최대로 자랄 수 있는 길이를 구해야 합니다. 2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 .. 2022. 9. 18.
[구현/그리디] 백준 2828 사과 담기 게임 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M 2022. 9. 15.
[우선순위큐/그리디] 백준 1715 카드 정렬하기 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 문제 풀이 여러 개의 정렬된 카드 묶음(deck)을 하나로 합치는 데에 필요한 최소 비교횟수를 구해야 합니다. 2022.02.20 - [Algorithm] - [Algorithm] 힙(heap), 최소/최대로 정렬하는 우선순위 큐 [Algorithm] 힙(heap), 최소/최대로 정렬하는 우선순위 큐 그래프의 트리 구조 중 하나인 '힙'과 구현 방법에 대해 알아보고, 그와 관련된 우선순위 큐도 .. 2022. 9. 12.
[그리디/Greedy] 백준 9237 이장님 초대 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net 2. 문제 풀이 묘목이 다 자라는 데에 필요한 시간이 주어집니다. 하루에 1개만 심을 수 있으며, 모두 다 자라는 데에 필요한 최소의 일 수를 구해야 합니다. 2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 경주마들을 자세히 보면, 양쪽 시야를.. 2022. 9. 9.

티스토리툴바