그리디
-
[백준] 4796 캠핑 with PythonPS 2023. 4. 14. 14:23
📌 BOJ 4796 캠핑 💡 조건 등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다. 캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다. 캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠동안 사용할 수 있을까? (1 < L < P < V) 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. 그리디 유형의 문제 🔖 예제 및 실행결과 예제 1 5 8 20 5 8 17 0 0 0 실행결과 1 Case 1: 14 Case..
-
[백준] 1789 수들의 합 with PythonPS 2023. 4. 3. 16:26
📌 BOJ 1789 수들의 합 💡 조건 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 첫째 줄에 자연수 N의 최댓값을 출력한다. 수학, 그리디 알고리즘 유형의 문제 🔖 예제 및 실행결과 예제 1 200 실행결과 1 19 ⌨️ 문제 풀이 계산하고 있는 계산값(A), 정답(B), 더할 수(C)를 각각 변수로 만든다. while를 이용해 반복적인 계산을 한다. A += C 후, C += 1, B += 1 (2)번의 반복문은 A가 입력 받은 S 보다 작을때만 반복한다. while 의 조건에 해당되지 않아 반복문이 종료되었으면 조건에 맞게 출력한다. 만약 A가 S와 값이 같다면 ans를, 그게..
-
[백준] 14469 소가 길을 건너간 이유 3 with PythonPS 2023. 4. 1. 22:41
📌 BOJ 14469 소가 길을 건너간 이유 3 💡 조건 N마리의 소가 이 농장에 방문하러 왔다. 소가 도착한 시간과 검문받는 데 걸리는 시간은 소마다 다르다. (물론 같을 수도 있다.) 두 소가 동시에 검문을 받을 수는 없다. 예를 들어, 한 소가 5초에 도착했고 7초 동안 검문을 받으면, 8초에 도착한 그 다음 소는 12초까지 줄을 서야 검문을 받을 수 있다. 모든 소가 농장에 입장하려면 얼마나 걸리는지 구하는 문제. 첫 줄에 100 이하의 양의 정수 N이 주어진다. 다음 N줄에는 한 줄에 하나씩 소의 도착 시각과 검문 시간이 주어진다. 각각 1,000,000 이하의 양의 정수이다. 정렬, 그리디 유형의 문제 🔖 예제 및 실행결과 예제 1 3 2 1 8 3 5 7 실행결과 1 15 ⌨️ 문제 풀이 기..
-
[백준] 11508 2+1 세일 with PythonPS 2022. 5. 9. 20:35
📌 BOJ 11508 2+1 세일 💡 조건 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 됩니다. 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 합니다. 유제품의 수 N (1 ≤ N ≤ 100,000) N개의 줄에는 각 유제품의 가격 Ci (1 ≤ Ci ≤ 100,000) 정답은 231-1보다 작거나 같다. 최소비용으로 유제품을 구입할 수 있도록 도와주는 문제. 그리디, 정렬 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin arr = [] n = int(stdin.readline()) for i in range(n): arr.append(int(stdin.readline())) arr.sort(re..
-
[백준] 1411 비슷한 단어 with PythonPS 2021. 12. 12. 03:25
📌 BOJ 1411 비슷한 단어 💡 조건 문자열 A를 숌스럽게 바꾸어 B로 만들었다면, 그 단어는 비슷한 단어라고한다. 숌스럽게 바꾼다는 것은 단어 A에 등장하는 모든 알파벳을 다른 알파벳으로 바꾼다. 단어가 여러 개 주어졌을 때, 몇 개의 쌍이 비슷한지 구하는 문제. 단어의 길이는 최대 50 N은 100보다 작거나 같은 자연수이다. 모든 단어의 길이는 같고, 중복되지 않는다. 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin from itertools import combinations words = [] res = set() tc = int(stdin.readline()) if tc == 1: print(res) else: for _ in range(tc): wor..
-
[백준] 11497 통나무 건너뛰기 with PythonPS 2021. 12. 6. 21:07
📌 BOJ 11497 통나무 건너뛰기 💡 조건 첫 줄에 통나무의 개수를 나타내는 정수 (5 ≤ N ≤ 10,000) 둘째 줄에 각 통나무의 높이를 나타내는 정수 (1 ≤ Li ≤ 100,000) 통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 그리디 알고리즘유형의 문제 🖥 소스 코드 from sys import stdin for _ in range(int(stdin.readline())): n = int(stdin.readline()) arr = list(map(int, stdin.readline().split())) arr.sort() res = 0 for i in range(2, n): res = max(re..
-