본문 바로가기
728x90

JAVA/백준100

[Java] 백준 1256 사전 - 조합 알아보기(7) 백준 1256 사전 문제 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다. 규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다. N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 .. 2023. 1. 3.
[Java] 백준 1722 순열의 순서 - 조합 알아보기(6) 백준 1722 순열의 순서 문제 1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다. 임의의 순열은 정렬을 할 수 있다. 예를 들어 N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이…. N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. .. 2023. 1. 2.
[Java] 백준 13251 조약돌 꺼내기 - 조합 알아보기(5) 백준 13251 조약돌 꺼내기 문제 효빈이의 비밀 박스에는 조약돌이 N개 들어있다. 조약돌의 색상은 1부터 M까지 중의 하나이다. 비밀 박스에서 조약돌을 랜덤하게 K개 뽑았을 때, 뽑은 조약돌이 모두 같은 색일 확률을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 M (1 ≤ M ≤ 50)이 주어진다. 둘째 줄에는 각 색상의 조약돌이 몇 개 있는지 주어진다. 각 색상의 조약돌 개수는 1보다 크거나 같고 50보다 작거나 같은 자연수이다. 셋째 줄에는 K가 주어진다. (1 ≤ K ≤ N) 출력 첫째 줄에 뽑은 조약돌이 모두 같은 색일 확률을 출력한다. 정답과의 절대/상대 오차는 10^-9까지 허용한다. 제출 import java.io.*; import java.util.*; public class Main .. 2023. 1. 1.
[Java] 백준 1010 다리 놓기 - 조합 알아보기(4) 백준 1010 다리 놓기 문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수.. 2022. 12. 31.
[Java] 백준 2775 부녀회장이 될테야 - 조합 알아보기(3) 백준 2775 부녀회장이 될테야 문제 평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다. 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다. 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다. 입력 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케.. 2022. 12. 30.
[Java] 백준 11051 이항 계수 2 - 조합 알아보기(2) 백준 11051 이항 계수 2 문제 입력 출력 제출 import java.util.*; public class Main { static int N, K; static int[][] D; public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(System.in); N = sc.nextInt(); K = sc.nextInt(); D = new int[N + 1][N + 1]; for (int i = 0; i 2022. 12. 29.
[Java] 백준 11050 이항 계수 1 - 조합 알아보기(1) 백준 11050 이항 계수 1 문제 입력 출력 제출 import java.util.*; public class Main { static int N, K; static int[][] D; public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(System.in); N = sc.nextInt(); K = sc.nextInt(); D = new int[N + 1][N + 1]; for (int i = 0; i 2022. 12. 28.
[Java] 백준 11438 LCA 2 - 최소 공통 조상(2) [Java] 백준 11437 LCA 2 문제 N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. 출력 M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다. 제출 import java.io.*; import java.util.*; public c.. 2022. 12. 27.
[Java] 백준 11437 LCA - 최소 공통 조상(1) [Java] 백준 11437 LCA 문제 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. 출력 M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다. 제출 import java.util.*; public class Main { static Arr.. 2022. 12. 26.
728x90

티스토리툴바