본문 바로가기

그리디12

[BOJ][Python]13305 풀이 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net n = int(input()) l = list(map(int, input().split())) p = list(map(int, input().split())) min_p = p[0] ans = 0 for i in range(1, len(p)): ans += l[i-1] * min_p if p[i] < min_p: min_p = p[i] print(ans) 정말 제가 그리디를 잘 안푼.. 2023. 7. 13.

[BOJ][Python]2810 풀이 https://www.acmicpc.net/problem/2810 2810번: 컵홀더 첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다. www.acmicpc.net n = int(input()) s = input() ans = 1 cnt = 0 for i in range(n): if s[i] == 'L': cnt += 1 if cnt % 2 == 0: ans += 1 print(min(ans, len(s))) 이번 내용은 어떻게 하면 L의 사이에는 컵홀더를 놓지 않을것인가를 고민하면 되는 문제였습니다. 저는 처음에는 좌석을 계속 비교하는 방식으로 코드를 작성했다가 L은 무조건 붙어서 나오기 때문에 L이 나온 횟수만 세어주면 비교하는 과정을 거치지 않아도 될.. 2023. 1. 23.

[BOJ][Python]18238 풀이 https://www.acmicpc.net/problem/18238 18238번: ZOAC 2 2019년 12월, 두 번째로 개최된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 작년 ZOAC의 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해 www.acmicpc.net from string import ascii_uppercase uppers = list(ascii_uppercase) s = input() ans = 0 start = 'A' for i in s: start_idx = uppers.index(start) next_idx = uppers.index(i) if next_idx > start_idx: ans += min((next_idx.. 2023. 1. 17.

[BOJ][Python]22864 풀이 https://www.acmicpc.net/problem/22864 22864번: 피로도 첫 번째 줄에 네 정수 $A$, $B$, $C$, $M$이 공백으로 구분되어 주어진다. 맨 처음 피로도는 0이다. www.acmicpc.net a, b, c, m = map(int, input().split()) work = 0 tired = 0 for _ in range(24): if tired + a > m: tired = 0 if tired < c else tired - c else: tired += a work += b print(work) 최근에 파이썬이 새로운 버전이 나오면서 속도가 엄청 빨라졌다고 들었는데 그 이유 때문인지 백준에서 파이썬 채점을 할 때 시간이 상당히 빠릅니다. 예전에는 아무리 짧은 코드.. 2022. 12. 31.

[BOJ][Python]14487 풀이 https://www.acmicpc.net/problem/14487 14487번: 욱제는 효도쟁이야!! 욱제는 KOI를 망친 기념으로 부모님과 함께 코드게이트 섬으로 여행을 떠났다. 코드게이트 섬에는 오징어로 유명한 준오마을(심술쟁이 해커 임준오 아님), 밥으로 유명한 재훈마을, 영중마을 등 www.acmicpc.net n = int(input()) num = list(map(int, input().split())) max_num = max(num) num.remove(max_num) print(sum(num)) 이번 문제는 모든 마을을 다 갈 수 있는 최단 거리를 구하는 문제입니다. 사실 최단거리라고 말하기도 좀 그런게 마을은 전부 섬 외곽에 위치해있고 다른 마을로 이동하기 위해서는 무조건 섬 외곽을 .. 2022. 12. 30.

[BOJ][Python]2864 풀이 https://www.acmicpc.net/problem/2864 2864번: 5와 6의 차이 첫째 줄에 두 정수 A와 B가 주어진다. (1 2022. 12. 29.

[BOJ][Python]5585 풀이 https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net price = int(input()) change = 1000 - price ans = 0 coin = [500, 100, 50, 10, 5, 1] for i in coin: coin_num = change // i change -= i*coin_num ans += coin_num print(ans) 이번 문제는 그리디 알고리즘의 대표적인 문제 중 하나인 동전 갯수 문제입니다.. 2022. 12. 28.

[BOJ][Python]1783번 풀이 https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net n,m = map(int, input().split()) if n >= 3: if m >= 7: print(m-2) elif m >= 4: print(4) else: print(m) elif n == 2: if m >= 7: print(4) else: print(1+(m-1)//2) else: print(1) 이번에는 구현 문제인데요. 느낌이 그리디랑 비슷한 문제입니다. 뭔가 수학적인 계산을 하는 문제라기 보다는 논리적 추론에 가까운 문제가 아닌가 생각합니다. .. 2022. 7. 10.

[BOJ][Python]2720번 풀이 https://www.acmicpc.net/problem/2720 2720번: 세탁소 사장 동혁 각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다. www.acmicpc.net t = int(input()) d = [25,10,5,1] for _ in range(t): c = int(input()) ans = [] for i in d: ans.append(c//i) c %= i print(*ans) solved.ac 사이트에서 개인 정보를 확인하면 어떤 알고리즘의 문제를 많이 풀었는지 그래프로 나타내주는 기능이 있는데요. 그리디를 하나도 안 푼 수준으로 안풀었더군요. 그래서 그런가 실버 상위권 그리디 문제가 나오면 자주 막히는 것 같아서 예.. 2022. 6. 27.

[BOJ][Python]1931번 풀이 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net import sys ssr = sys.stdin.readline n = int(ssr()) c = [list(map(int, ssr().split())) for _ in range(n)] c.sort(key= lambda x:(x[1], x[0])) cnt = 1 end = c[0][1] for i in range(1, n): if c[i][0] >= end: cnt += 1 end = c[i][1] print(cnt) 이번 문제는 푸는 방법을 어떻게든 생각해내는게 전부인 문제입니다. 다르게 말하면 푸는 방법을 .. 2022. 6. 21.

이전 1 2 다음

티스토리툴바