문제 풀이https://www.acmicpc.net/problem/1943 처음엔 가능한 동전 집합에 다음 동전을 하나씩 더하며 새로운 경우를 추가해가며 전체 금액의 합/2를 만들어 보려 했으나... 메모리 + 시간이 말도안되기에 계속해서 터졌다. 갈피를 못잡다 결국 아래 블로그를 보고 이해를 했다https://blog.naver.com/adamdoha/222086394461 1943번 : 동전 분배문제 링크 : https://www.acmicpc.net/problem/1943 문제를 해결한 방법 웰논 DP 문제에서 아이디어를 떠...blog.naver.com설명이 너무 잘되어 있어 추가 설명은 하지 않겠다.. 코드import java.io.BufferedReader;import java.io.IOExc..
문제 풀이https://www.acmicpc.net/problem/13144주어진 N 길이의 수열에 대해 연속된 1개 이상의 수를 뽑았을 때 중복되지 않는 경우의 수를 구하면 된다. 이걸 조금 쪼개서 생각해보면중복되지 않은 수열 A에 포함된 수 a가 추가될 때 경우의 수를 구해나가는 방식으로 쪼갤 수 있다.즉, 1 2 3 이라는 수열에 1,2,3중 하나가 추가되는 경우를 생각해볼 수 있다. 각 경우에 대해 추가 후 새롭게 A를 만드는 경우는 아래 3가지다.1 2 3 + 1 -> 2 3 11 2 3 + 2 -> 3 22 3 + 3 -> 3 또 여기서, 새롭게 A를 만들기 전에 기존 배열을 활용하여 만들 수 있는 경우의 수는1 / 1 2 / 1 2 31 / 1 2 / 1 2 3 / 2 / 2 31/ 1 2..
문제 분석https://www.acmicpc.net/problem/26311~N의 번호가 마킹된 어린이를 순서대로 정렬하려 할 때 가장 적은 이동으로 정렬시킨다면 이때 이동 횟수를 구하는 문제다. 처음 떠올렸던 방법은각 아이를 기준으로 왼쪽 중 자신보다 번호가 큰 아이들의 연속된 횟수오른쪽 중 자신보다 번호가 작은 아이들의 연속된 횟수를 각각 구하고 이중 가장 큰 연속값을 가진 아이를 왼쪽 혹은 오른쪽으로 연속 횟수만큼 옮겨주는 방식으로 구현했었다.근데.. 무슨 반례가 있는 지 잘 모르겠지만.. 4%에서 계속 실패했고 게시판을 봐도 별다른 반례가 없어 결국 LIS로 다시 풀기로 했다. LIS로 풀면 아주 간단하다.. 그냥 주어진 배열에서 LIS의 길이를 구하고 전체 배열의 길이에서 빼주면 이게 정답이 된..
문제 분석https://www.acmicpc.net/problem/2179N개의 영단어가 주어진다.각 단어는 알파벳 소문자로 이루어졌고, 최대 100의 길이를 가진다.단어는 최대 2만개까지 주어진다. 이때, 공통의 접두사가 최대가 되는 가장 빠른 두 단어를 찾아야 하는 문제다.즉, ABCD - ABCE 처럼 ABC를 공통 접두사로 가지고, 이때 접두사의 길이가 최대이며 두 단어가 입력받은 순서 기준으로 제일 빠르다면 가장 빠른 두 단어가 된다. 조건에서 모든 단어는 중복되지 않는다고 하였기에 입력에 대한 별다른 중복검사를 해줄 필요는 없고, 동일한 단어를 두번 검사해서는 안된다. 입력받은 순서를 기억하기 위해 index와 word내용 자체를 저장하는 객체 Word를 만들고 이를 PQ에 넣어 저장했다. 그..
문제 분석https://www.acmicpc.net/problem/1238각 지점에서 X로 또, X에서 각 지점으로 최소의 비용으로 움직일 때전체 지점 중 왕복 비용의 최댓값을 구하는 문제다. 다익스트라를 순방향, 역방향으로 2번 사용하여 풀 수 있다. max cost를 처음에 너무 낮게 잡아 계속 틀렸었으나..각 마을간 도로는 1개고 순환 도로는 없으니 max cost는 마을의 갯수 * 도로의 최대 비용이다. 즉, 1000*100이다.코드import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextI..
문제 풀이https://www.acmicpc.net/problem/14658n*m 구역에 k개의 별똥별이 주어지고 l*l 크기의 정사각형 트램펄린으로 이를 최대한 많이 튕겨냈을 때부딪히게 되는 별똥별의 수를 구하는 문제다 n*m 좌표에 대해 접근하거나 l의 길이에 대해 탐색을 하게 된다면 각 50만, 10만으로 수가 꽤 크기에 시간초과 혹은 메모리 초과가 발생할 가능성이 높다. 하지만, k가 100으로 매우 작기에 k^3의 풀이도 10^6으로 통과될 수 있다. 트램펄린에 별똥별이 최대로 담기고 최적으로 담기는 경우에 대해 생각해보면O O O O OO * * O OO * O O OO O * O O이런식으로 최대 4개를 가둘 수 있다고 생각할 수 있지만 이게 최적의 트램펄린 배치는 아니다.(왼변, 윗..
문제분석https://www.acmicpc.net/problem/24337맨 왼쪽에서 봤을때 보이는 빌딩의 수 a맨 오른쪽에서 봤을때 보이는 빌딩의 수 b그리고 전체 빌딩의 수 n 가 주어진다. 이때 만들 수 있는 빌딩 높이 배열 중 사전순으로 가장 빠른 높이 배열을 찾아 출력하는 문제다. 문제를 조금 나누어 생각해보면a b인 경우로 나눠진다 맨 왼쪽에서 a개의 빌딩을 보는 높이 배열 중 가장 사전 순으로 빠른 경우는1 ... 1 2 3 .. a 이다. 반대로 맨 오른쪽에서 b개의 빌딩을 보는 가장 사전 순으로 빠른 경우는 1 .. 1 b b-1 b-2 .. 1이다. 하지만 a != b인 경우 1 .. 1 2 .. a b ... 1의 배열로 빌딩이 서있을 때왼쪽 또는 오른쪽에서 보이는 빌딩의 갯수가..
문제 코드https://www.acmicpc.net/problem/9935input으로 주어지는 문자열과짧은 길이의 폭탄 문자열이 주어진다. input 내에 폭탄 문자열이 포함된다면 해당 문자열은 사라지게 된다.또한 이 폭발은 연쇄적일 수 있다. 폭발이 끝난 후 남는 문자열을 구하여 반환하라 처음 풀이는 StringBuilder에 input 원소를 하나씩 집어넣고원소 c가 폭탄 문자열의 bombIndex의 값과 같다면1. bombIndex를 증가시킨다.2. 만약 bombIndex가 마지막 index를 넘어섰다면, c를 포함한 앞의 bomb 길이 만큼 문자열이 터진다.반대로, 다르다면 현재까지의 문자열은 폭탄을 구성하지 않기에 bombIndex를 초기화해준다. 이때, 터진 문자열은 boolean 배열을 ..
