미니감자

문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)출력첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. k원을 만드는데 필요한 동전의 최소개수는 가장 먼저 큰 동전을 사용하면 된다. 예를 들어 4200원을 만드려면 1000원짜리 4개와 100원짜리 2개를 사용하면 되는 것이다. i..

문제인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. ..

문제숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도..

문제영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다.입력첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열은 공백으로 시작하거나 끝날 수 있다.출력첫째 줄에 단어의 개수를 출력한다.첫번째 방법은 자바에서 제공하는 trim 메서드를 활용해서 푸는 방법이다.trim메서드는 문자열의 앞과 뒤에 있는 모든 공백(스페이스, 탭, 줄바꿈 등)을 제거한 새로운 문자열을 반환해준다. import java.util.Scanner;..

문제재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 ..

하노이 탑은 3개의 막대가 있고 원반을 목표 막대로 옮기는 과정이다. 이 과정에서1. 한번에 한개의 원반만 움직일 수 있다.2. 가장 위에 있는 원반만 움직일 수 있다.3. 큰 원반이 작은 원반 위에 있을 수 없다.위와 같이 3개의 규칙을 지켜야한다. 원반의 개수를 n이라고 한다면n = 1일때A->C총 1번이 걸린다. n = 2일때 A->BA->CB->C총 3번이 걸린다. n=3일 때A->B(가장 큰 원반 한개만 남겨놓고 나머지 다 B로 이동)- A->C- A->B- C->BA->C(가장 큰 원반 한개 A에서 C로 이동)B->C(B에 남아있는 원반들 C로 이동. )- B->A- B->C- A->C총 7번이 걸린다. 일반식을 유도해보면f(n) = 1+2f(n-1)이라는 것을 알 수 있다.왜냐하면 가장 큰 ..

재귀함수란?재귀함수(Recursion Function)는 자기 자신을 스스로 호출하여 작업을 수행하는 함수이다. 재귀는 문제를 더 작은 부분으로 나누어 해결하는 방식으로, 주로 반복되는 작업이나 분할 정복 알고리즘에 사용된다. 재귀함수는 크게 두 가지 부분으로 구성된다.Base Case : 더 이상 재귀 호출을 하지 않고 함수를 종료하는 조건이다. Base Case가 있어야 무한 루프에 빠지지 않고 종료될 수 있다.Recursive Case : 함수가 자기 자신을 호출하는 부분이다. public class recursionEx { public static int factorial(int n){ if(n  위의 코드에서는 if(n이 Base case에 해당하고 return n*factorial(n-1);..

문제N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 이 문제는 정렬만 하면 간단한 문제인 것 같아서 버블정렬을 사용하여 구현해 보았다.import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int arr[] = new i..