백준 알고리즘 파이썬(Python) 20115번 에너지드링크
2021. 5. 14. 15:49
Algorithm
그리디 문제를 풀다보면 정렬을 어떻게 하느냐가 문제의 Key인 경우가 많다 이 문제 역시 그러하다. 이 문제의 핵심은 에너지 드링크의 양을 내림차순으로 정렬하고 가장 양이 많은 에너지 드링크를 제외하고 2번째 부터 쭉 절반으로 나눈 값을 더해 result를 갱신해주는 것이다 n = float(input()) k = list(map(int, input().split())) #에너지 드링크 양을 k 리스트에 저장 k.sort(reverse = True) #에너지 드링크 양 내림차순으로 정렬 result = 0 count = 1 for i in k: if count == 1: #첫번째 에너지 드링크는 그대로 result 값에 넣어준다 count += 1 result += i continue else: resu..
백준 알고리즘 파이썬(Python) 11508번 2+1 세일
2021. 5. 14. 13:42
Algorithm
크게 어렵지 않은 문제다. 조금만 고민해 보면 입력받은 유제품의 가격을 큰 순서대로 내림차순으로 정렬한 다음 3의 배수의 자리의 있는 숫자를 제거해주고 다 더해주면 답이라는 것을 알 수 있다 이 문제의 핵심은 내림차순으로 정렬 후 3의 배수 자리의 숫자를 없애준다 이다 n = int(input()) cost = [] #유제품 가격 리스트 for i in range(n): a = int(input()) cost.append(a) cost.sort(reverse = True) #가격을 내림차순으로 정렬 count = 1 #리스트 안의 순서를 세주는 count 값 1로 지정 result = 0 for i in cost: if count%3 != 0: result += i count += 1 else: #만약 ..
백준 알고리즘 파이썬(Python) 1758번 알바생 강호
2021. 5. 9. 21:25
Algorithm
이 문제의 핵심은 팁을 받은 순서를 큰 순서대로 리스트에 배열하는것 이다 만약 1, 1, 9, 9 가 주어진다 생각해보면 작은 숫자 즉 1이 줄의 뒤로가면 어느순간 돈 - (반은 등수 - 1) 의 값이 음수가 나온다. 따라서 1은 2번째 부터는 어디에 줄을 서든 어차피 팁은 0원이다 하지만 큰 숫자는 뒤로 갈수록 원래 주려고 했던 팁이 줄어든다. 즉 팁을 최대로 받을 수 있는 최적의 방법에서 멀어진다는 얘기다. 그리디 알고리즘은 최적의 결과값을 도출해내는게 목적이다. n = int(input()) #사람의 수 N이 주어짐 tip = [] #tip을 넣을 리스트 생성 for _ in range(n): a = int(input()) tip.append(a) tip.sort(reverse = True) #줄 ..
백준 알고리즘 파이썬(Python) 13305번 주유소
2021. 5. 2. 01:57
Algorithm
일반적인 그리디 문제처럼 이문제에서 중요한 것은 리스트를 만들어 알맞은 값으로의 최신화이다 핵심은 왼쪽에서부터 순차적으로 도시의 기름값을 확인하여 min값을 최신화 해주는 것이다. 그리디의 핵심은 가장 최적의 경우를 탐색해 찾아내는 것 n = int(input()) #도시개수를 입력받는다. road = list(map(int, input().split())) #도시 사이의 거리를 입력받는다. city = list(map(int, input().split())) #도시의 기름값을 입력받는다. min_val = city[0] #min_val 값을 첫 도시의 기름값으로 price_sum = 0 #price_sum 0으로 초기값 설정 for i in range(n-1): if min_val > city[i]: ..
백준 알고리즘 파이썬(Python) 1343번 폴리오미노
2021. 4. 16. 22:07
Algorithm
뭔가 그리디스럽지 않다고 생각한 문제이다. 처음에는 당연히 ' . ' 를 기준으로 split 해야하는줄 알고 많이 헤맸던거 같다 (뭐 안헤매는 문제가 적지는 않지만...) 그러다 문득 split 하지 않고 문자열로 생각해 보면 쉽지 않을까 라는 생각이 들었고 그 결과 단 몇줄만의 코드로 풀이가 가능하다는 것을 알았다. 이 문제의 핵심은 replace의 정확한 사용법을 아느냐 이다. 만약 'XXXXX' 이렇게 연속된 5개의 X가 있을때 replace('XXXX', 'AAAA')를 해준다면 replace는 각각의 인덱스, 즉 0의 위치부터 순서대로 'XXXX'를 찾아내어 그것을 명령대로 바꿔준후 다시 'XXXX'를 찾아나선다 즉 'AAAAX' 이렇게 변한다는 뜻이다. 그동안 replace를 공부할때는 [ '..