그리디12 백준 [자바 java] 12904 : A와 B https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 처음에는 dfs로 풀었는데 시간초과가 났다. 그래서 더 효율적인 방법을 찾다가 완성된 문자열에서 처음 문자열로 돌아가는 방법을 쓰게 되었다. 문자열의 제일 끝이 A이면 이전에 기존 문자열 끝에 A를 썼다는 의미이므로 A를 뺴고 그대로 두면 되고, B이면 B를 빼고 문자를 뒤집으면 된다. 이를 반복하다가 문자가 아예 사라지면 break를 통해 나오고 안된다는 결.. 2023. 8. 4. 백준 [자바 java] 11399 : ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제도 예전에 c언어로 풀었어서 java로 다시 한번 풀었다. 사람마다 atm을 이용하는 시간이 주어지고 이를 사용하는 사람들이 기다리는 전체 시간의 최솟값을 출력하는 문제이다. 이때 이용시간이 작은 사람 순서대로 정렬한 후 이 순서대로 atm을 이용하면 되니까, 정렬한 후 여기다가 (전체사람 수 - 해당 수의 배열 순서)를 곱하면 된다. (첫번째 사람이 돈을 뽑을 동안 기다리는 사람들의 수는 전체이고, 두번째 사람이 돈을.. 2023. 7. 23. 백준 [자바 java] 1541 : 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 식이 주어지고 해당 식에 괄호를 적절히 쳐서 최종 값을 작아지게 만드는 문제이다. 해당 식은 더하기와 빼기만 있다. 이를 최대한 작게 만드려면 최대한 작은 수를 더하고 큰 수를 빼야한다. 따라서 괄호는 -를 제외하고 전부 넣어주면 된다. ex) 55 - (50 + 40) 77 - (55 + 30 + 2) - (44) - (41 + 25) 나는 식을 입력받으면 -를 기준으로 이를 split하고.. 2023. 7. 23. 백준 [자바 java] 1026 : 보물 https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 이 문제는 두 배열이 주어지고 두 배열간의 곱한 값을 더한 값이 최소가 되게 하는 문제이다. 핵심은 곱하는 두 수가 둘 다 큰 수이면 수가 많이 커지니까 이를 적절하게 조합하는 것이다. 가장 큰 수에는 가장 작은수를 곱하는 과정을 하기 위해서 두 배열을 다 정렬한 후 첫번째 배열은 앞에서부터, 두번째 배열은 뒤에서부터 곱해서 더해나가면 답을 구할 수 있다. import java.util.*.. 2023. 7. 23. 백준 [자바 java] 2839 : 설탕배달 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 1년 전에 c언어로 풀었던 문제인데 이번 학습동아리를 위해 자바로 다시 풀었다. 이 문제는 그리디 알고리즘을 설명할 수 있는 가장 간단한 문제라고 생각한다. 최대한 적은 수의 봉지를 사용해서 설탕을 옮기는 방법을 구하는 문제인데, 이를 위해서는 5킬로그램 봉지를 최대한 많이 사용해야하면서도, 이를 사용하고 남은 설탕의 그람수가 3으로 나누어 떨어져야 한다. 따라서 나는 주어진 설탕의 수를 5로 나눈 후 이 .. 2023. 7. 23. 백준 [java 자바] 1092 : 배 https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 배들이 한번에 적재 할 수 있는 최대 무게가 나와있는 상태에서, 주어진 상자를 옮길 수 있는 시간의 최솟값을 구하는 문제이다. 나는 현재 남은 화물들을 차례대로 배에 실으면서 시간을 재는 방법을 선택했다. 처음에는 우선순위큐를 사용하려고 했으나, 최대무게를 저장해놓은 배열과 비교하는 과정에서 훨씬 복잡해질 것 같아서 linkedlist를 사용했다. 그리고 시간을 최소화 하기 위해서.. 2023. 7. 18. 이전 1 2 다음
