일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 백준 1197번 최소 스패닝 트리 - java
- 백준 1806번 부분합 java
- HashSet
- append
- 백준 1647번 도시 분할 계획 - java
- replace()
- 코틀린기초
- 프로그래머스
- StringTokenizer
- hash
- 프로그래머스 java
- 백준 2467번 용액 자바 - 이분탐색
- 프로그래머스 자바
- mysql hy000 에러
- Java
- map
- kotlin
- 백준 1541
- HashMap
- Stack
- toUpperCase
- 백준 3190번
- dp
- StringBuilder
- 18111번 마인크래프트 - java 구현
- 백준 2473번 세 용액 - java
- 백준 14938번 서강그라운드
- ac 5430번
- 백준 1043번 거짓말 - java 분리 집합
- 최소 힙 1927
Archives
- Today
- Total
말하는 컴공감자의 텃밭
알고리즘 재활 13일차 - 15663, 1149, 1753번 본문
728x90
N과 M (9)
중복되는 수열을 제외하고 출력해주는게 포인트이다
따라서 정렬한 arr 배열에서 수로 수열을 만들때 이전 수와 같은지 체크해주었다.
if (!visit[i] && arr[i] != prev)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | import java.io.*; import java.util.*; public class Main { // N과 M (9) public static int N, M; public static StringBuilder sb; public static boolean[] visit; public static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); sb = new StringBuilder(); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); arr = new int[N]; visit = new boolean[N]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < N; i++) { arr[i] = Integer.parseInt(st.nextToken()); } Arrays.sort(arr); dfs(0, new int[M]); System.out.println(sb); } public static void dfs(int depth, int[] nums ) { if (depth == M) { for (int s : nums) { sb.append(s).append(" "); } sb.append("\n"); return; } int prev = -1; for (int i = 0; i < N; i++) { if (!visit[i] && arr[i] != prev) { visit[i] = true; nums[depth] = arr[i]; prev = arr[i]; // 현재 값을 이전 값으로 업데이트 dfs(depth + 1, nums); visit[i] = false; } } } } | cs |
RGB거리
간단한 DP 문제였다,
1자로 집이 나열되어 있기 때문에 이전 집만 고려해주면 됐다.
따라서 i 번째 집의 색은 이전과만 다르게 DP로직을 구성하고 DP 배열에 저장된 마지막 인덱스의
최소값을 찾아주면 된다.
간단한 점화식
dp[i][0] = (Math.min(dp[i-1][1], dp[i-1][2])) + arr[i][0];
dp[i][1] = (Math.min(dp[i-1][0], dp[i-1][2])) + arr[i][1];
dp[i][2] = (Math.min(dp[i-1][1], dp[i-1][0])) + arr[i][2];
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | import java.io.*; import java.util.*; public class Main { // RGB거리 public static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); int [][] arr = new int[N][3]; int [][] dp = new int[N][3]; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); for(int j = 0 ; j < 3 ; j++) { arr[i][j] = Integer.parseInt(st.nextToken()); } } for(int i = 0; i < 3; i++) { dp[0][i] = arr[0][i]; } for(int i = 1; i < N; i++) { dp[i][0] = (Math.min(dp[i-1][1], dp[i-1][2])) + arr[i][0]; dp[i][1] = (Math.min(dp[i-1][0], dp[i-1][2])) + arr[i][1]; dp[i][2] = (Math.min(dp[i-1][1], dp[i-1][0])) + arr[i][2]; } int answer = Math.min(dp[N-1][0], Math.min(dp[N-1][1], dp[N-1][2])); System.out.println(answer); } } | cs |
최단경로
방향그래프 였던 거시와요..
우선순위 큐 활용해서 가중치가 낮은것부터 해당 위치에 가는 비용을 갱신해줍시다.
다익스트라로 해결~
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | import java.io.*; import java.util.*; public class Main { // 최단경로 public static int V, E, K; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); V = Integer.parseInt(st.nextToken()); E = Integer.parseInt(st.nextToken()); K = Integer.parseInt(br.readLine()); List<List<Node>> graph = new ArrayList<>(); for (int i = 0; i <= V; i++) { graph.add(new ArrayList<>()); } int[] cost = new int[V + 1]; Arrays.fill(cost, Integer.MAX_VALUE); cost[K] = 0; for (int i = 0; i < E; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); graph.get(u).add(new Node(v, w)); } dijkstra(K, graph, cost); StringBuilder sb = new StringBuilder(); for (int i = 1; i <= V; i++) { if (cost[i] == Integer.MAX_VALUE) { sb.append("INF\n"); } else { sb.append(cost[i]).append("\n"); } } System.out.println(sb.toString()); } public static void dijkstra(int start, List<List<Node>> graph, int[] cost) { PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.cost)); pq.add(new Node(start, 0)); while (!pq.isEmpty()) { Node cr = pq.poll(); int crNode = cr.idx; int crCost = cr.cost; if (crCost > cost[crNode]) continue; for (Node n : graph.get(crNode)) { int newCost = crCost + n.cost; if (newCost < cost[n.idx]) { cost[n.idx] = newCost; pq.add(new Node(n.idx, newCost)); } } } } static class Node { int idx; int cost; Node(int idx, int cost) { this.idx = idx; this.cost = cost; } } } | cs |
728x90
'알고리즘 > Backjoon - Java' 카테고리의 다른 글
알고리즘 재활 15일차 - 11723, 1927, 5430번 (0) | 2024.08.19 |
---|---|
알고리즘 재활치료 14일차 - 10816, 15666, 1504번 (0) | 2024.08.16 |
알고리즘 재활 12일차 - 백준 2869, 15654, 16236번 (0) | 2024.08.14 |
알고리즘 재활 11일차 - 백준 9461, 5525, 1389번 (0) | 2024.08.14 |
알고리즘 재활 10일차 - 백준 테트로미노 14500번 (0) | 2024.08.12 |
Comments