그리디알고리즘16 [Baekjoon] 1789 - 수들의 합 📝 문제 🔑 풀이 과정 · 처음에 문제가 너무짧아서 이해조차 못했던 문제이다...! · 서로 다른 N개의 자연수를 더해서 S를 만들어야 할때, N의 최댓값을 구하는게 목표이다. 즉, 더해야하는 자연수가 많아야하므로 작은 자연수들부터 더해서 수를 만들어야 한다. · N의 각 경우마다, 만들수 있는 수의 최솟값을 먼저 보겠다. N=1 일 때, 최솟값은 1 = 1 이다. N=2 일 때, 최솟값은 1+2 = 3이다. N=3 일 때, 최솟값은 1+2+3 = 6이다. N=4 일 때, 최솟값은 1+2+3+4 = 10이다. 그럼 여기서 5를 만들려면 자연수가 몇개 필요할까? 답은 2이다.3개로 표현할수 있는 가장 작은수가 6이기 때문이다. (5는 6보다 작음) · 즉, 각 자연수를 N개써서 만들수 있는 최솟값과 입력받.. 2023. 8. 25. [Baekjoon] 1758 - 알바생 강호 📝 문제 🔑 풀이 과정 · 한 사람이 내는 팁: 원래 주려고 생각했던 돈 - (받은 등수 - 1) 등수가 뒤로 갈수록 차감되는 팁의 액수가 많아진다. 즉, 강호가 최대로 팁을 받으려면, 팁의 액수가 큰 사람일수록 앞 등수에 배치해야 한다. · 팁을 내림차순으로 정렬한 뒤, 원래 주려고 생각했던 돈 - (받은 등수 - 1) 식을 사용해서 팁의 총액을 계산한다. 주의해야 할 점은, 계산된 팁이 음수라면 강호는 팁을 받을 수 없다는 점이다. → 식의 결과가 음수라면 팁이 0원 🔓 답안 import java.io.*; import java.util.ArrayList; import java.util.Collections; public class Main { public static void main(String[.. 2023. 8. 16. [Baekjoon] 2847 - 게임을 만든 동준이 📝 문제 🔑 풀이 과정 · 입력받은 레벨의 점수를 적당하게 감소시켜서 오름차순으로 만들어 주면 되는 문제. 즉, 배열의 요소를 다음 인덱스가 가리키는 요소보다 작게 만들면 되는 것 · 배열을 뒤부터 순회하면서, 현재 가리키는 인덱스가 i라면, 인덱스 i+1이 가리키는 요소보다 i가 가리키는 요소를 작게 만들면 된다. 나는 while문을 사용해서 이를 구현했다. · 가장 최소한으로 내리는 방법을 구해야 하므로, 작아지면 바로 다음순서로 넘어간다. (4 5 5 가 있으면 3 4 5 로 만드는게 최소, 굳이 2 4 5, 1 2 3 이런식으로 만들 필요가 없음) 🔓 답안 import java.io.*; public class Main { public static void main(String[] args) th.. 2023. 8. 12. [Baekjoon] 1049 - 기타줄 📝 문제 🔑 풀이 과정 · 일단 이 문제를 풀때 주의점 3가지 ① 하나의 브랜드 것만을 사는것이 아니다. 패키지는 A브랜드에서, 낱개는 B브랜드에서 구입할 수 있다. ② 패키지가 무조건 낱개 * 6보다 싼것이 아니다. 예제 2의 마지막 입력을 보면 패키지(6개입)은 60, 낱개는 4임을 볼 수 있다. ③ 필요한 기타줄 수 이상으로 사도 상관 없다. 만약 9개의 기타줄이 필요하면, 패키지 2개(12개입)을 사도 된다. 금액만 최소가 보장되면 가능하다. · 예제 2를 예시로 들어서 설명해보면, 필요한 기타줄의 수는 10개이다. 이런경우 구매할 수 있는 가짓수가 3가지로 나뉜다. ① 패키지 2개 구입 + 낱개 0개 구입 (기타줄 12개) ② 패키지 1개 구입 + 낱개 4개 구입 (기타줄 10개) ③ 패키지 0.. 2023. 8. 10. [Baekjoon] 4796 - 캠핑 📝 문제 🔑 풀이 과정 · V: 캠핑장을 사용할 수 있는 전체 기간 · 캠핑장을 최대한 많이쓰려면, P일중 앞의 L일을 사용하면 되는것이다. · 풀이를 그림으로 나타낸 것 - (V를 P로 나눈 몫 * L)을 일단 구해준다. - 그 후, (V - (V를 P로 나눈 몫 * P)) 가 L보다 크거나 같다면 L을 더해주고, 작으면 그 값 자체를 더해준다, 🔓 답안 import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syst.. 2023. 8. 6. [Baekjoon] 1541 - 잃어버린 괄호 📝 문제 🔑 풀이 과정 · 우리가 구해야 하는 것 = 주어진 식의 값을 최소로 만들기 (식은 +, -로만 이루어짐) · 주어진 식의 값을 최소로 만드려면 뺄셈을 할 때, 뒷 항을 최대한 크게 만들어 주면 된다. 뒷 항을 최대한 크게 만드려면 +를 사용해서 항을 최대한 크게 만들어주면 된다. · 풀이 방식 ① 우선 입력을 '-' 기준으로 여러 식으로 끊어준다. ② 식 중 맨 앞 식은 모든 항을 +로 더해줘야 한다. ③ 나머지 식들은 모든 항을 -로 빼줘야 한다. · 글로 보면 이해가 잘 안될수도 있으니, 예시를 보자 · 이 문제는 String의 split() 함수를 사용해서 풀이했는데, split() 함수는 인자를 정규 표현식으로 받는다 한다. 정규 표현식에서 특수문자를 분할 기준으로 사용하려면 이스케이프.. 2023. 7. 16. 이전 1 2 3 다음
