본문 바로가기

💜💜💜115

조합수 (메모이제이션) 설명로 계산합니다.하지만 여러분은 이 공식을 쓰지않고 다음 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요. 입력첫째 줄에 자연수 n(3 출력첫째 줄에 조합수를 출력합니다. 예시 입력 1 5 3 예시 출력 110 예시 입력 2 33 19 예시 출력 2818809200  문제 해결 조합을 계산하는 문제이다.조합에서 C(n,r)=1인 경우는n==r 또는 r==0인 경우이고, 그 외의 경우에는 조합의  C(n−1,r−1)과 C(n−1,r)의 합을 반환해 재귀를 이용하며 ㅣ용해주면 된다.   최종 코드 import java.util.Scanner;public class P07_조합수_메모이제이션 { static int n, r; public static void main(Stri.. 2024. 5. 11.
순열 구하기 설명10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 입력첫 번째 줄에 자연수 N(3두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다. 출력첫 번째 줄에 결과를 출력합니다.출력 순서는 사전순으로 오름차순으로 출력합니다. 예시 입력 1 3 23 6 9 예시 출력 13 63 96 36 99 39 6  문제 해결 static int N, M;static int[] arr;static int[] selected;static boolean[] visited;static String result = "";숫자의 개수 N, 순열을 만들 때 선택할 숫자의 수 M입력으로 주어지는 자연수를 저장하는 arr 배열선택된 숫자를 저장하는 데 사용하는 selected 배열해당 숫.. 2024. 5. 11.
동전교환 설명다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?각 단위의 동전은 무한정 쓸 수 있다. 입력첫 번째 줄에는 동전의 종류개수 N(1그 다음줄에 거슬러 줄 금액 M(1 출력첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다. 예시 입력 1 31 2 515 예시 출력 13 힌트출력 설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.  문제 해결 이 문제는 동전의 종류와 각각의 동전을 무한히 사용할 수 있을 때, 주어진 금액을 만들기 위해 필요한 최소 동전 수를 계산하는 문제이다. static int N, M;static int[] money;static int[] minCoins; // M원을 만드는 데 필요한 최소 동전 수 배열stat.. 2024. 5. 11.
중복순열 구하기 설명1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락해 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 입력첫 번째 줄에 자연수 N(3 출력첫 번째 줄에 결과를 출력합니다.출력순서는 사전순으로 오름차순으로 출력합니다. 예시 입력 1 3 2 예시 출력 11 11 21 32 12 22 33 13 2 3 3 문제 해결 이 문제는 N과 M에 대해 중복 순열을 만들어 출력하는 문제이다. 중복 순열은 각 요소가 한 번 이상 선택될 수 있는 순열을 을 말한다. 예를 들어 N이 3이고 M이 2라면, (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)와 같이 각 번호가 여러 번 선택될 수 있는 것이다. static int N,.. 2024. 5. 11.
최대점수 구하기(DFS) 설명 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)입력첫 번째 줄에 문제의 개수N(1두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다. 출력첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다. 예시 입력 1 5 2010 525 1215 86 37 4 예시 출력 141 문제 해결 제한된 시간 내에 가능한 최대 점수를 얻기 위해 주어진 문제들 중에서 선택하는 방법이기.. 2024. 5. 11.
바둑이 승차(DFS) 설명철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요. 입력첫 번째 줄에 자연수 C(1둘째 줄부터 N마리 바둑이의 무게가 주어진다. 출력첫 번째 줄에 가장 무거운 무게를 출력한다. 예시 입력 1 259 58158423361 예시 출력 1242 문제 해결 철수가 가지고 있는 바둑이들 중에서 무게 C 를 초과하지 않으면서 가장 무거운 무게로 바둑이들을 트럭에 실을 수 있는 무게를 구하는 문제이다. 이는 DFS를 이용해 해결할 수 있다.  public class P.. 2024. 5. 10.
반응형

티스토리툴바