기록방

👉 문제링크 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 🔸 문제 분석 🔸 중간 원소를 기준으로 오름차순 후 내림차순이 이어지는 수열을 바이토닉 수열이라고 한다. 주어지는 수열의 부분 수열 중 가장 긴 바이토닉 수열의 길이를 출력한다. 🔸 문제 풀이 🔸 각 인덱스 별로 가장 긴 오름차순 수열과 가장 긴 내림차순 수열의 길이를 따로 구해 저장한다. 같은 인덱스의 두 값의 합 중 최대값을 출력한다. 🔸 코드 🔸 import java.io.*; import java.util.StringTokenizer; public class Ma..

👉 문제링크 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 🔸 문제 분석 🔸 n개의 노드와 m개의 단방향 간선 정보가 주어진다. 시작 노드부터 목적지 노드까지의 경로 중 비용이 최소값이 되는 경로를 찾아, 비용과 경로 상의 노드 수 및 경로를 출력한다. 같은 최소값이면서 다른 경로일 수 있는데, 모두 정답으로 인정된다. 🔸 문제 풀이 🔸 다익스트라 알고리즘으로 최단경로를 구한다. 비용의 최소값 뿐만 아니라 최단경로를 출력해야 하므로, 값이 경신될 때 이전 출발 노드의 번호를 저..

👉 문제링크 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 🔸 문제 분석 🔸 기본 문자열과 폭발 문자열이 입력된다. 기본 문자열에서 폭발 문자열 부분이 폭발하며 지워지고, 남은 문자열은 다시 이어 붙는다. 더 폭발할 문자열이 남지 않았을 상태의 문자열을 출력한다. 남은 문자가 없으면 "FRULA"를 출력한다. 🔸 문제 풀이 🔸 문자열의 길이가 100만이기 때문에 O(n^2) 미만의 알고리즘을 사용해야 한다. 반복문 한 번에 계산할 수 있도록 한다. 새로운 문자열이 생기면 메모리 문제가 생길 수..

👉 문제링크 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 🔸 문제 분석 🔸 10 이하의 자연수 N이 주어지고, N-1 개의 재료 비율이 주어진다. 칵테일을 만드는데 필요한 각 재료의 최소 질량을 출력한다. 🔸 문제 풀이 🔸 기준값을 찾기 위해 입력된 p, q 비율들의 최소공배수를 구한다. N개의 재료와 N-1의 연결 정보는 N개의 노드와 N-1의 간선 정보이므로 트리 형태로 나타낼 수 있다. 한 노드에 값을 넣고 DFS로 인접한 노드를 탐색하며 입력된 비율로 각 노드의 질량 값을 만들어 간다. 모든 노드의..

👉 문제링크 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 🔸 문제 분석 🔸 A와 B의 길이만큼 1로 이루어진 수의 최대공약수를 구하는 문제이다. 🔸 문제 풀이 🔸 실제 수는 아주 긴 1로 이루어진 숫자들이지만, 그냥 A와 B의 최대공약수를 구하면 되는 문제이다. 유클리드호제법을 사용해서 최대공약수를 구하고, 그 수만큼 반복해서 1로 이루어진 수를 만들어 출력한다. 🔸 코드 🔸 import java.io.*; import java.util.StringTokenizer; public cl..