문제 분석https://www.acmicpc.net/problem/1253N개의 수가 주어지고 각 수마다 해당 숫자를 자신을 제외한 서로 다른 두 수의 합으로 만들어낼 수 있는지 판단하고 그렇다면 좋은 수로 여긴다.이때 좋은 수의 갯수를 구하는 문제. N은 2000까지, 값은 절댓값기준 10억 이하 정수N이 작기에 n^2의 풀이도 통과될 수 있다. 처음엔 간단하게 for loop를 2번 돌리며 가능한 모든 수의 합을 Set에 넣고 배열에 대해서 있으면 ans ++ 하는 방식으로 구현했었다. 즉, 0~n-2의 인덱스 i에 대해 i+1 ~ n-1의 인덱스와의 합을 Set에 저장했다. 그런데, 생각해봐야 하는 부분이 있다.0 + k 는 k다. 여기서, 합쳐진 결과 k는 자기자신을 사용하였기에 문제의 조건에 어..
문제 분석https://www.acmicpc.net/problem/4485전형적인 bfs문제다.보드가 주어지고 0,0에서 n-1,n-1로의 경로 중 가장 저렴한 비용으로 갈 때 그 비용을 묻는 문제였다. point마다 해당 point까지 온 cost를 저장하고 이를 PQ에 낮은 순으로 삽입한다.또, point에 방문했을 때 굳이 더 비싼 비용으로 도착한 경우 탐색을 이어나갈 필요가 없기에 이 부분도 같이 체크해주면 된다. 코드import java.util.*;public class Main { public static void main(String[] args) throws InterruptedException { Scanner sc = new Scanner(System.in); ..
문제 분석https://www.acmicpc.net/problem/1107티비의 채널을 N으로 변경하려하는데M개의 숫자 버튼이 고장나있다.그리고, +,- 버튼이 존재한다.100번에서 N번 채널으로 최소한의 버튼 조작으로 이동할 때 그 이동 횟수를 구하는게 문제다. 처음에 앞의 자리수 부터 가장 가까운 수를 넣어 최적의 이동 횟수를 구하는 방법을 생각해봤었는데생각해보면 10000이라는 숫자에 대해서 1에 가장 가까운 유효한 수는 2지만 9999가 더 가깝다. 그런데, 주어진 N의 범위가 500000 밖에 되지 않는다.즉, 10^6가지의 숫자만 고려해주면 되고 이정도는 충분히 돌아도 제한 시간을 만족하게 된다. 따라서 나는 아래와 같은 구조로 문제를 풀었다. 주어진 숫자의 길이 -1 의 숫자 중 가장 큰 수..
문제분석https://www.acmicpc.net/problem/1365 X -> Y로 하나의 전선씩 연결되어 있는데, 이 중 최소의 전선을 잘라 전선끼리 겹치는 것이 없게 만드는 것이 목적이다. 전선이 서로 겹치지 않기 위해선 최종적으로 남는 각 전선 쌍들이 단조적이여야 한다.즉, 1-2 / 2-3/ 3-4 이런식으로 서로 겹치지 않아야 한다. 이런 순차적인 쌍들의 최댓값을 찾는 것이 최소의 전선을 자르는 방법이기에 이 문제는 LIS(최장 증가 부분수열) 알고리즘으로 접근할 수 있다. N = 10^5 이기에 O(N^2)으론 시간을 맞출 수 없다. https://velog.io/@min-ji99/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B0%80%EC%9E%A5-%EA%B..
문제분석https://www.acmicpc.net/problem/10330~N-1의 인덱스 사이의 비율 p/q를 주고이걸 바탕으로 각 인덱스에 해당하는 재료를 정수로 만들었을 때 그 합이 최소가 되게 만들라는 문제다. 따라서1. 인덱스 0과 연결된 노드는 최소 1개 이상 존재하기 때문에 (칵테일을 제조할 수 있다는 전제가 있음) 해당 노드를 찾아 두 노드를 기준으로 삼는다 (비율이 p/q면 a,b의 질량을 p,q로 산정한다) (당연히 p,q는 서로소다)2. bfs로 인접 노드끼리 비교하며 모든 노드간 비율을 구한다.3. 유클리드 호제법을 통해 최소공배수를 구한다https://programmer-chocho.tistory.com/9 [JAVA] 최대 공약수(GCD), 최소 공배수(LCM) 구하기최대 공약수..
문제풀이https://www.acmicpc.net/problem/1016 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다. 문제가 아주 심플하다. 그렇지만1 ≤ min ≤ 1,000,000,000,000min ≤ max ≤ min + 1,000,000범위가 악랄하다. 10^12이니 단순히 1번만 돌아도 무조건 timeout이라는 것min~max의 범위가 10^6 밖에 되지 않는다는 것을 염두에 두고 풀이를 해야 한다. 주어진 조건을 조금 변형해보자.제곱 ㄴㄴ수가 아닌 제곱 ㅇㅇ수를 구해보자.즉, X가 1보다 큰 제곱수로 나..
문제 분석https://www.acmicpc.net/problem/1013주어진 정규식에 해당하는 문자열인지 판단하는 로직을 만들면 되는 문제다. 난도 자체는 쉽겠지만 문제는 경우의 수를 정말 잘 따져야 한다.. 나는 문자를 1개씩 붙여보며 가능성이 있는 지 판단하는 방식으로 구현했다. idx를 증가시켜가며 StringBuilder에 char를 계속 append하고해당 StringBuilder의 크기를 기준으로1 -> 패턴이 될 가능성이 있음2 -> 01은 패턴이니 sb 초기화 ,10 은 패턴이 될 가능성이 있음3-> 100은 패턴이 될 가능성이 있음4up -> 0이 추가된 경우 -> 직전이 0이였다면 100000...의 형태로 패턴이 될 가능성이 있음 ..
문제 분석https://www.acmicpc.net/problem/1202무게와 가격을 가진 N개의 보석이 있고최대 C의 무게까지 담을 수 있는 가방에 최대 1개의 보석을 담을 수 있으며 이런 가방이 K개가 있을 때 담을 수 있는 최대 가치를 구하는 문제다. 맨 처음에는 냅색같이 생겼다 싶었는데, 잘 읽어보니 K개에 최대 1개만 담을 수 있다고 적혀있었다. 다음으로 떠올렸던건 세그먼트 트리인데1. N개의 보석에 대해서 무게 순으로 쭉 정렬을 하고2. 각 무게의 시작 index를 저장하는 Map을 만들고3. 정렬된 배열을 기반으로 하는 최댓값 세그먼트 트리를 만들고4. 들어오는 가방마다그리디하게 0부터 해당 가방 크기에 해당하는 구간까지의 최댓값을 구하고5. 사용된 보석의 가치를 0으로 만들고 세그먼트 ..
