알고리즘/Greedy5 [Greedy] 백준 1339 : 단어수학 - 파이썬 Python 생각하기 N개의 단어가 주어졌을 때 가장 큰 자리수를 가진 알파벳에 가장 큰수를 순서대로 주면 될거 같다고 생각했다 가중치가 있으면 좋다고 생각을 했다 각 자리수에 따라 10단위의 가중치를 주기로 했다 5번째 자리 : 10000 4번째 자리 : 1000 3번째 자리 : 100 2번째 자리 : 10 1번째 자리 : 1 각각의 알파벳의 자리수 위치에 따라 각 자리수에 해당하는 가중치를 더한다. 구현하기 가중치를 더할 때, 알파벳 딕셔너리에 넣기위해 인덱스(숫자)화 해야 했다 물론 그냥 문자 그대로 딕셔너리에 넣어도 되지만 접근을 쉽게 하기 위해 숫자화 해주었다 ord('A') : 'A' character를 ascill코드로 바꾸어 준다 alpha_score 이라는 딕셔너리에 각 알파벳에 대한 가중치 값을 지.. 2021. 11. 12. [Greedy] 큰수를 만들기 문제 배열(arry)에 들어가 있는 수를 M번 더하여 가장 큰수를 만드는 방식 단 배열의 특정 위치에 해당하는 수가 연속 K번 더해질 수는 없음 예시 ) K=3, M=5일때 5, 4, 2, 6, 7 -> 7+7+7+6+7 가장 큰수를 만드는 것이기 때문에 data들을 정렬하여 가장 큰 수를 찾는다 정렬의 경우에는 logN의 시간이 걸리는 최대 heap을 사용함 가장 큰수를 K번 더하면 더 더할 수 없으니 두번째 수를 한번 더하고 다시 가장 큰수를 더한다 즉, 가장 큰수와 두번째로 큰수를 번갈아(K번 + 1번) 더하면 됨 import sys import heapq input = sys.stdin.readline arry = [] N, M, K = map(int, input().split()) data = .. 2021. 8. 6. [Greedy] 백준 19639번 - 배틀로얄 일단 정답률이 27%라서 쫄았다 오늘 하루는 이거겠구나 하는 생각으로 시작한다 i번째 줄의 수 Vi가 음수라면, i번째 행동에 −Vi번째 적을 죽인다. i번째 줄의 수 Vi가 양수라면, i번째 행동에 Vi번째 아이템을 먹는다. 준석 제외 플레이어 수 = X 체력 회복 아이템 수 = Y 준석의 처음 및 최대 체력 = M (짝수) 준석이의 체력 잃는 양 그렇게 먹으나 1/2 초과 될때까지 포션들 집어 먹는 것이나 똑같지 않나? -> 그래서 예제에서는 크기 상관없이 1번째(3) 죽이고 2번째(5)죽이고 그랬구나? => 1/2 초과될 때까지 포션 먹는 것으로! 3. 그렇다면 포션 총 회복량 + M 사실상 적들을 치는 순서가 .. 2021. 1. 18. [Greedy] 백준 11047번 - 동전 0 동전을 최대한 적게 이용하려면 큰 값의 동전부터 넣어보아야 한다. 예를 들어 6500원을 만들어야 하고 1000원이 가장 큰 돈 단위라면 1000원부터 6장 넣고 그다음에 남은 500원을 처리하는 것이 더 효율적이다 하지만! 큰 단위의 동전을 넣을 수 있는 만큼 넣었는데 나머지 돈 단위로 해결할 수 없는 애매한 잔액이 남았다면? 그렇다면 한단계 전으로 돌아가서 뺀 다음에 다시 진행 Case 1) 선택한 동전으로 차감할 수 있는 경우 선택한 동전이 K보다 작아야 한다 Case 2) 선택한 동전으로 차감 불가한 경우 다음 작은 동전으로 넘어간다 애초에!!!! Case 1만 남기기 위해 사전에 값을 넣을 때 K보다 큰 수는 vector에 넣지 않는다 최대로 차감할수 있는 동전의 개수를 아는 법 : 남은 돈 /.. 2021. 1. 18. 이전 1 2 다음