[Java] 백준 2294 동전 2

문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. 출력 첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다. 문제 링크 : 동전 2 설명 얼마 전 푼 동전 1과 비슷한 문제라서 점화식도 사실 어렵지 않게 세웠다. 그래서 호기롭게 제출을 했으나... 84% 에서 틀렸습니다 를 보고 ..

• format_list_bulleted 알고리즘
• · 2024. 1. 6.
• textsms

[Java] 백준 2293 동전 1

문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 문제 링크 : 동전 1 설명 주어진 N개의 동전을 사용해서 K를 만들 수 있는 경우의 수를 구하는 문제이다. 처음에 규칙을 잘못 찾아서 "음?" 했던 문제이다.....

• format_list_bulleted 알고리즘
• · 2024. 1. 4.
• textsms

[Java] 백준 9461 파도반 수열

문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 출력 각 테스트 케이스마다 P(N)을 출력한다. 문제 링크 : 파도반 수열 설명 주어진 ..

• format_list_bulleted 알고리즘
• · 2023. 12. 30.
• textsms

[Java] 백준 1916 최소비용 구하기

문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M..

• format_list_bulleted 알고리즘
• · 2023. 12. 29.
• textsms

[Java] 백준 1912 연속합

문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력 첫째 줄에 답을 출력한다. 문제 링크 : 연속합 설명 처음에 점화식을 도출해내는 과정에서 이중 반복문을 돌려고 했었다. 그런데 n이 최대 10만이고 이중 반복문을 돌면..

• format_list_bulleted 알고리즘
• · 2023. 12. 28.
• textsms

[Java] 백준 30974 What's your ETA?

문제 진주 나들이를 온 보선이는 버스를 타고 미리 예약해놓은 진양호 전망대에 가기 위해 가까운 버스 정류장에 도착했다. 그런데 이상하게 버스정보안내단말기에 단 한 대의 도착 정보도 표시되지 않았다. 당황한 보선이가 여기저기 알아보던 도중, 보선이의 대학 동기인 준희로부터 문자 한 통이 왔다. 맛이 어때? 알고 보니 이는 준희가 한 짓이었다. 대학생 때 국밥 마니아 보선이 때문에 매일 국밥만 먹게 되었던 리조또 마니아 준희는 지금까지 앙심을 품고 있었다. 마침 준희는 보선이가 진주에 놀러 왔다는 사실을 알게 되었고, 천재적인 해킹 실력을 발휘해 버스정보시스템을 해킹하여 시내버스가 다니지 못하게 만들었던 것이다. 하지만, 진주에는 Super Bus라는 재난 대비 버스가 있었다. 진주시는 버스정보시스템이 해킹..

• format_list_bulleted 알고리즘
• · 2023. 12. 28.
• textsms