본문 바로가기

백준32

백준 [java 자바] 9084 : 동전 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 이 문제를 보자마자 언젠가 풀었던 문제인 것 같은데? 라는 생각이 들긴 했다. dp를 사용하고, 점화식을 구해서 풀어야 한다는 것 까지는 알아냈지만 여기서 어떻게 해야 할지 도저히 감이 잡히지 않아서 사람들의 풀이법을 검색해서 배웠다. 일단 풀이법을 그림으로 정리해보았다. 글씨가 정말 별로지만, 이해하는데는 확실히 도움이 되었다. 일단, 동전의 수가 주어지고 동전의 액수가 들어오면.. 2023. 7. 25.
백준 [자바 java] 2252 : 줄 세우기 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 4개월 전에 풀려고 시도했다가 못 푼 문제를 다시 풀어봤다. 학생의 수와 키를 비교한 횟수가 주어진다. a와 b가 주어지면, a가 무조건 b앞에 있어야 한다는 의미이다. 나는 list를 두 개를 놓고, 하나는 학생마다 뒤에 와야 하는 학생을 저장하고, 하나는 앞에 오는 학생을 저장하는 리스트를 만들었다. a와 b를 입력받으면, list[b]에 a를 넣고,.. 2023. 7. 24.
백준 [자바 : java] 1038 : 감소하는 수 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 수를 입력받으면 감소하는 수 중 해당 수번째 감소하는 수를 출력하는 프로그램이다. 처음에는 수학적인 규칙을 찾으려고 했지만 쉽지 않았고, 감소하는 수가 많이는 없다는 것을 알고, 모든 감소하는 수를 찾아 정렬하고 구하는 방식을 사용했다. 처음에는 순열을 이용해서 풀었는데 0을 다루는 과정에서 오류가 났다. arr에서의 순서대로 수를 구성하면 첫 자리가 0일 때를 간과하게 되기 때문이.. 2023. 7. 24.
백준 [자바 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.

티스토리툴바