빙응의 공부 블로그

배수 공사 시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초128 MB95536030341.057%문제영만이네 집은 너무 오래되어서 변기에 물이 줄줄 샌다. 보다 못한 영만이는 마침 집에 파이프가 남아 있어서 직접 배수 공사를 하려고 한다.하지만 파이프를 자르는 비용이 너무나 비싸기 때문에, 가난한 영만이는 남은 파이프들을 적절히 모아서 원하는 길이로 만들어야 한다. 영만이가 가지고 있는 파이프의 길이와 그 수량을 알고 있을 때, 파이프를 적당히 합쳐서 x만큼의 길이를 만드는 방법의 수를 구하시오. 파이프를 합치는 순서는 고려하지 않는다.입력영만이가 가지고 있는 파이프의 종류의 수 N과 만들고 싶은 합친 파이프의 길이 x가 주어진다. (1 ≤ N ≤ 100 이며, 1 ≤ x ≤ 10 000 이다.)다음..

📝 풀이첫번째로 생각한 것은 DFS로 풀이였습니다. import java.util.*;class Solution { static HashSet hs; public int solution(int n, int[] money) { hs = new HashSet(); Arrays.sort(money); dfs(n, money, new int[money.length], 0); return hs.size(); } public static void dfs(int n, int[] money, int[] count, int start) { if (n == 0) { hs.add(Arrays.toString(count..

📝 기본 아이디어 기본적인 불량 사용자 매핑으로는 풀 수 없는 문제이다. 그 이유는 불량 사용자 중에 동일한 목록이 나올 수 있기에 중복 계산이 되어 크게 나올 수도 있기 때문이다. 또한 제한사항이 그렇게 크지 않아  DFS도 가능하다.불량 리스트 별로 가능한 user_id 들을 저장HashSet을 이용해서 중복되는 루트를 거름결과 또한 HashSet으로 저장하여 쉽게 결과 도출 import java.util.*;class Solution { Set> result = new HashSet(); public int solution(String[] user_id, String[] banned_id) { List> possibleBans = new ArrayList(); ..

📝 기본 아이디어제한 사항sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.제한 사항을 보면 배열이 10만 이하로 완전 탐색이나, DFS, BFS는 좋지 않습니다.그렇기에 DP로 풀겠다고 마음먹었습니다. 기본 아이디어DP로 시작 시 0번 스티커를 때면 마지막 스티커를 사용할 수 없다는 것을 처리해줘야 합니다.또한 이 로직이 진행되기 전에 길이가 1이면 먼저 리턴을 해줘야 자연스럽게 오류 없이 풀..

📝풀이해당 문제는 기본 아이디어를 세우는 게 중요하다. 자연수 S를 자연수 집합 N개로 나눠야한다. 집합 N개로 나눈 경우의 수 중에 곱이 가장 큰 것을 구하라이 두개를 잘 보면 쉽게 구할 수 있다. 그건 바로 집합 N개로 나눌 때 곱이 가장 큰 것은 집합이 가장 균등해야 가능하다. 즉 n = 3 s = 10이면 균등 값은 [3, 3, 4]여야 한다. 가장 쉽게 식을 세우면 s / n만으로 모든 집합 값을 결정할 수 있다.class Solution { public int[] solution(int n, int s) { int[] answer = new int[n]; // n보다 s가 작으면 집합으로 못나눔 if(n > s) return ne..

📝 풀이 기본 구조를 가지면 다음과 같다. 1234510    2 0   3  0  4   0 5    0 여기서 이제 승패를 1, -1로 표시하면 다음과 같이 나온다. 12345101   2-10-1-113 10-1 4 110 5 -1  0 문제에서 설명하는 순위를 알 수 있는 것은 자신을 제외한 모든 사람과의 시합을 알 수 있는 사람 즉 모든 배열이 채워진 사람을 말한다. 즉 모든 로직이 끝났을 때 자신을 제외하고 배열에 0이 없는 사람을 검사하면 된다.  [Arogorithm]그래프 - 플로이드워셜 [Arogorithm]그래프 - 플로이드워셜플로이드 워셜은 그래프에서 최단 거리를 구하는 알고리즘이다.최단 거리 문제는 다익스트라, 벨만포드, 플로이드 워셜이 있다.기능특징시간복잡도모든 노드 간에 최단..