728x90
https://www.acmicpc.net/problem/2157
DP 문제로 처음에 생각해내기 어려웠다..
풀이
1. 리스트 배열을 만들어서 배열의 인덱스는 출발지, 리스트에는 도착지와 점수를 넣는다. ( 만일, 도착지가 출발지보다 작은 수라면 동쪽이동이기 때문에 스킵!)
2. dp 이차원배열을 생성하여 "new int[몇번째로 방문한 것인지=> m+1][도착지 번호=>n+1] = 점수" 를 저장할 것이다.
3. 큐를 생성하여 출발지를 넣는다.
4. 맨 처음의 출발지는 1이고, 첫번째로 방문한 곳이기에 count=1
5. 큐에 담아 있는 곳들은 모두 같은 방문 번호를 같기에 size를 추출하여 포문을 돌린다.
6. 만일, 출발지로부터 온 점수보다 이미 dp에 저장되어 있는 점수가 더 높을 경우에는 스킵한다.
7. 그렇지 않다면, dp에 해당 값을 저장하고 큐에 해당 도착지를 넣는다.
8. dp[2~m번째로 방문][n]의 최대값을 찾아 출력한다! 끝!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n, m, k;
static int result=0;
static class Node{
int idx;
int point;
Node(int idx,int point){
this.idx=idx;
this.point=point;
}
}
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());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
ArrayList<Node>[] map= new ArrayList[n+1];
for(int i=1;i<=n;i++) {
map[i]= new ArrayList<>();
}
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
if(e<s) continue;
map[s].add(new Node(e,p));
}
int[][] dp = new int[m+1][n+1];
Queue<Integer> q = new LinkedList<>();
q.add(1);
int count=1;
while(!q.isEmpty()&&count<m) {
int size = q.size();
for(int z=0;z<size;z++) {
int idx=q.poll();
for(Node node:map[idx]) {
if(dp[count][idx]+node.point<=dp[count+1][node.idx]) continue;
dp[count+1][node.idx]=dp[count][idx]+node.point;
q.add(node.idx);
}
}
count++;
}
for(int i=2;i<=m;i++) {
result=Math.max(result, dp[i][n]);
}
System.out.println(result);
}
}
'Java' 카테고리의 다른 글
[백준 2228] 구간 나누기 (JAVA) (0) | 2023.07.12 |
---|---|
[백준 1947] 선물 전달 (JAVA) (0) | 2023.07.11 |
[백준 1398] 동전 문제 (JAVA) (0) | 2023.06.27 |
[백준 17609] 회문 (JAVA) (0) | 2023.06.21 |
[백준 2258] 정육점 (JAVA) (0) | 2023.06.20 |