목록전체 글 (60)

쫑쫑이의 블로그

백준 17404 RGB거리 2 Java [DP]

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 저번에 풀었던 RGB거리 문제와 비슷하지만 N번 집과 1번 집이 다른 색으로 칠해져야하는 조건이 추가됐다 첫번째 집에 칠하는 색에 따라 dp를 따로 해서 마지막 줄에서 다른 색 비용을 더한 값 중에서 최소값들을 비교해주면 된다 첫 두줄을 미리 계산하고 다음 줄부터 dp를 해줬다 import java.io.*; import java.util.*; public class ..
알고리즘/백준 2022. 10. 23. 21:01
백준 14003 가장 긴 증가하는 부분 수열 5 Java [LIS]

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 접근법은 이전에 푼 문제들과 동일하지만 부분 수열을 출력해야한다 A의 요소마다 인덱스값을 저장하는 배열을 만들고 뒤에서부터 값을 하나씩 줄여가면서 size 크기의 배열을 만든다 앞에서부터 만들면 다음 값이 작아지는 구간에 대처하기가 힘들다 뒤에서부터 접근하면 size가 8일때 최초로 등장하는 8미만의 수를 배열에 담아서 출력하면 된다 import java.io...
알고리즘/백준 2022. 10. 22. 16:20
백준 12738 가장 긴 증가하는 부분 수열 3 Java [LIS]

https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 이전에 푼 가장 긴 증가하는 부분 수열 2 문제보다 수열 A를 이루는 숫자가 범위가 더 크고, 음수도 들어온다 푸는 방법은 다르지 않지만 이번에는 Arrays.binarySearch 메서드를 사용해서 풀이를 해봤다 Arrays.binarySearch 메서드 값은 일치하는 숫자가 있으면 해당 인덱스를 반환하고, 일치하는 숫자가 없으면 절대값으로 바꾸고 -1 해주면 들어..
알고리즘/백준 2022. 10. 22. 09:58
백준 12015 가장 긴 증가하는 부분 수열 2 Java [LIS]

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net N이 1000000까지니까 NlogN 안으로 풀어야한다 예제 A 10 20 10 30 20 50 D 1 2 1 3 2 4 예제는 중복되는 숫자가 있어서 규칙을 찾기가 힘들다 예제 2 A 11 20 10 30 19 50 D 1 2 1 3 2 4 거리배열을 만들어서 배열 가장 끝값보다 크면 배열에 추가해준다 배열보다 작으면 이진탐색으로 작은값 중에 가장 큰값 찾아서 그 다음 인덱스 값과 교체해준다 i..
알고리즘/백준 2022. 10. 22. 03:40
백준 1644 소수의 연속합 Java [에라토스테네스의 체]

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수를 구하는 방법은 2가지 있다 1. 숫자를 증가시켜가면서 소수로 나눠지는지 확인하기 2. 에라토스테네스의 체 사용하기 숫자가 충분히 크니까 에라토스테네스의 체를 사용하는게 시간복잡도 측면에서 이득 에라토스테네스의 체는 2부터 시작해서 2를 제외한 2의 배수를 다 소수가 아니라고 체크하고 3을 제외한 3의 배수를 다 소수가 아니라고 체크한다 숫자를 증가시켜가면서 체크안된 숫자(소수)의 배수를 소수가 아니라고 체크하는 과정을 반복한다 그리고 연속된 수의 합이 N이면 count 해준다 이 방법은 숫자를 하나씩 증가시켜..
알고리즘/백준 2022. 10. 22. 01:50
백준 1504 특정한 최단 경로 Java [다익스트라]

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라로 1 -> v1 -> v2 -> N 과 1 -> v2 -> v1 -> N 중 가능한 짧은 경로를 찾아 출력하면 된다 import java.io.*; import java.util.*; public class Main { static int N; static List[] nodes; static final int INF = 700_000_000..
알고리즘/백준 2022. 10. 20. 23:17
이전 Prev 1 ··· 4 5 6 7 8 9 10 Next 다음