본문 바로가기

Algorithm

 (28)
[JAVA]문자열 뒤집기(Baekjoon) 문제 문제 영어 알파벳 대문자로만 구성된 문자열이 N개 있다 (S[1], S[2], ..., S[N] 이라 칭하자). Reverse(T)는 임의의 문자열 T를 뒤집은 문자열 이라 하자 (명백히, 모든 문자열 T에 대해 Reverse(Reverse(T)) = T 이다). 가령 Reverse("ABC") = "CBA" 이다. 당신은 N개의 문자열 각각에 Reverse() 함수를 적용할지 말지 고를 수 있고, 이를 통해 문자열이 사전순으로 정렬되도록 하고 싶다 (문자열이 N개 이므로 2N 가지의 방법이 존재한다). 각 문자열에 Reverse() 함수를 적용한 경우를 '1' 적용하지 않은 경우를 '0'으로 나타내면, 길이가 N인 0-1문자열이 된다 - 이를 "리버스 문자열" 이라 하자. (리버스 문자열은 길이가..
[JAVA]합분해(Baekjoon) 문제 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력 1 20 2 예제 출력 1 21 예제 입력 2 6 4 예제 출력 2 84 풀이 처음 문제를 잘못 이해해서 고생을 했다. 하지만, 문제를 완벽히 이해하는 게 우선이기에 계속 다시 읽어 이해했다. DP 문제를 찾아 풀었기 때문에 DP를 사용해야 한다는 것을 알고 시작한다. 직관적으로, DP로 풀려고 ..
[JAVA]평범한 배낭(Baekjoon) 문제 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 입력 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000..
[JAVA]별 찍기 - 11(Baekjoon) 문제 입력 첫째 줄에 N이 주어진다. N은 항상 $3×2^k$ 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 예제 입력 1 24 예제 출력 1 * * * ***** * * * * * * ***** ***** * * * * * * ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * * * ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * * * * * * * * * * * * * * * * * ..
[JAVA]특별상이라도 받고 싶어(Baekjoon) 문제 문제 HCPC 2021에 참석한 $N \times N$명의 사람들이 의자가 정사각형 형태로 배치된 대회장에서 대회를 한다. 모든 의자에는 서로 다른 추첨번호가 적혀있으며 HCPC 2021의 마지막에는 아래에 설명된 규칙에 따라 특별상을 받을 사람 한 명을 정한다. 특별상을 받을 수 있는 사람이 한 명이라면, 그 사람이 뽑힌다. 그렇지 않은 경우, 대회장을 같은 크기의 정사각형 네 개로 나누어 각 구역에서 이 규칙을 재귀적으로 적용해서 구역마다 한 명씩 총 네 명을 뽑는다. 뽑힌 네 명 중 의자에 적힌 추첨번호가 두 번째로 작은 사람이 뽑힌다. HCPC 2021에 참가한 지원이는 자신의 실력이 부족해서 수상권이 아니라고 생각하였고, 실력과 무관하게 받을 수 있는 특별상을 노리고 있다. 아래 예시를 참..
[JAVA]두 수의 합(Baekjoon) 문제 문제 n개의 서로 다른 양의 정수 $a_1, a_2, ..., a_n$으로 이루어진 수열이 있다. $a_i$의 값은 1보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, $a_i + a_j = x (1 ≤ i < j ≤ n)$을 만족하는 $(a_i, a_j)$쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100,000, 1 ≤ x ≤ 2,000,000) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. 예제 입력 1 9 5 12 7 10 9 1 2 3 11 13 예제 출력 1 3 풀이 입력의 크기가 1,000,000이하이다. $O..
[JAVA]색종이(Baekjoon) 문제 문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다. 입력 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의..
[JAVA]3진법 뒤집기(Programmers) 문제 문제 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수입니다. 입출력 예 n result 45 7 125 229 입출력 예 설명 입출력 예 #1 n (10진법) n (3진법) 앞뒤 반전(3진법) 10진법으로 표현 45 1200 0021 7 따라서 7을 retrun 해야 합니다. 입출력 예 #2 n (10진법) n (3진법) 앞뒤 반전(3진법) 10진법으로 표현 125 11122 22111 229 따라서 229를 return 해야 합니다. 풀이 수를 n진법으로 바꾸는 연산은 나머지 연산을 반복하면 된다. 10진법 이상의 경우에..

티스토리툴바