알고리즘95 백준 [자바 java] 10986 : 나머지 합 문제설명연속된 수열이 있을 때 이 수열의 부분합이 특정 수로 나누어 떨어지는 경우의 수를 구하여라 풀이처음에는 b로 나누어떨어지는 덩어리를 구해서 이어지는 경우의 수를 구하는 방식으로 문제를 풀었지만 시간초과가 났다.그래서 다른 사람의 풀이를 봤는데 수학적인 부분을 사용해서 풀어야하는 문제임을 깨달았다.난 이런 쪽으로 좀 약한 것 같다... 일단 부분합을 구하는 것까지는 생각했다.12312배열이 있고, 3으로 나누어떨어지는 부분배열의 수를 구해야한다고 했을 때주어진배열12312합배열13679합 나머지배열10010 위와 같이 배열을 만든다.우리가 a에서 b까지의 부분합이 m으로 떨어지느냐를 알려면(합배열[b] - 합배열[a]) % m = 0 인지를 보면 된다. 기존 나의 방식은 이와 같았고, 시간초과가 났.. 2025. 3. 5. 백준 [자바 java] 16562번 : 친구비 문제설명준석이는 친구를 사귀기 위해서는 친구비를 내야한다.이 때 친구비를 내서 사귄 친구의 친구는 그냥 사귈 수 있다. 모든 친구를 사귀기 위한 친구비의 최소비용은? 풀이dfs로 풀었다. 한 무리를 탐색할 때마다 그 무리 중 친구비가 가장 적은 비용을 구한다.그 친구비의 합이 준석이가 가지고 있는 비용보다 작으면 Oh no를 출력한다.package org.example;import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in.. 2025. 3. 4. 백준 [자바 java] 1956번 : 운동 문제설명v개의 마을이 있고, 각 마을로 가는 비용이 주어질 때 특정 마을을 왔다갔다 하는 비용 중 가장 작은 비용을 구하는 문제이다. 풀이전형적인 다익스트라 문제이다.하나의 노드에 대한 다익스트라만 구하는 것이 아닌, 모든 노드에 대해서 구해야하므로 2차원배열을 사용하였다. for(int i = 1;i다익스트라 배열을 다 채운 후, 해당 값이 아직 Integer.MAX_VALUE인 경우 해당 노드는 거치치 않은 것으로 판단할 수 있기 때문에 배열 계산에서 제외했다.(MAX_VALUE와 MAX_VALUE를 더하면 오버플로우 발생할 수 있기 때문) if(ans == Integer.MAX_VALUE){ System.out.println(-1); } else System.out.printl.. 2025. 3. 4. 백준 [자바 java] 9466번 : 텀 프로젝트 문제설명n명의 사람들이 있고, 이 사람들이 원하는 팀원이 주어진다고 할 때, 그 어떤 팀에도 속하지 못하는 사람이 있을 수 있다. 이 사람들의 명수를 구하여라 풀이처음에는 혼자 팀을 하고싶어하는 사람과 팀을 하고싶어하는 사람들을 팀에 속하지 못하는 사람으로 분류하고, 또 그 사람과 팀을 원하는 사람을 제외하고.... 이런식으로 문제를 풀었는데 광탈을 해버렸다. 그래서 여러 반례를 찾아보니, 스스로와 팀을 원하는(혼자 팀을 원하는) 사람들이 없는데도, 팀을 이루지 못하는 경우도 있었다.사이클에 포함되지 못하는 경우! 그래서 이 경우를 제외해야한다. 역시,, 가능한 사람들을 보고 빼는게 맞는거같다. 이렇게 하니까 너무 많은 반례를 지나친다 그래서 while문을 통해 계속해서 탐색하다가 이미 방문한 노드를 마.. 2025. 3. 1. 백준 [자바 java] 1253번 : 좋다 문제설명n개의 수가 주어지고, 그 중 어떤 수가 다른 두 수의 합으로 나타낼 수 있으면 그 수를 좋다라고 한다.n개의 수 중 좋은 수의 갯수는? 풀이이 문제는 1년전 실패했었다..다시 보니까 그 이유가 좀 보였다!일단 3퍼에서 자꾸 틀렸습니다가 나왔는데 그 이유는 배열을 정렬하고 첫번째 수를 전혀 고려하지 않았기 때문이다. 하지만 이렇게 하면0 0 0 0일때 배열 내의 가장 작은 수도 좋은 수가 될 수 있는데 이를 간과해버린다. 또 60프로대에서 계속 틀렸습니다가 나왔는데 이건 좋은 수는 서로 다른 두 수를 더했을 때 좋다고 할 수 있는데, 투포인터를 하는 과정에서 지금 탐색하고 있는 수까지 포함시켜버렸다.예를 들어 2가 좋은 수인지 탐색하는데 2+0을 확인하고 좋은수라고 인식한 것이다. 그거 말고는 투.. 2025. 2. 27. 백준 [자바 java] 1238번 : 지름길 개념공부만 하니까 좀 지겨워서 백준을 풀었다. 문제설명https://www.acmicpc.net/problem/1238n명의 사람들이 있고, 그 사람들 사이를 지나다닐 때 걸리는 시간이 주어졌을 때, n명의 사람들 중 특정 사람(x)를 오고가는데 걸리는 시간이 가장 많은 사람의 시간을 구하는 문제이다 뭔가 외국어를 번역한 문제라 처음엔 이해가 좀 어려웠는데그냥 x까지 왕복하는 각각의 사람들에 대한 최소비용을 계산하고 이 최소비용의 최댓값을 구하면 되는 문제이다. 코드package org.example;import java.io.*;import java.util.*;public class Main { public static ArrayList> rode; public static int[][] ans;.. 2025. 2. 26. 이전 1 2 3 4 ··· 16 다음
