반응형

14494번 다이나믹이 뭐예요?

https://www.acmicpc.net/problem/14494

 

14494번: 다이나믹이 뭐예요?

(1, 1)에서 (n, m)에 도달하는 경우의 수를 구하여라. 단, 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007(=109+7)로 나눈 나머지를 출력한다.

www.acmicpc.net

Comment

DP문제의 기초격 문제

DP는 기초라고해도 왜이리 생각하기 어려운지 모르겠다..

hint

dp배열의 저장값 : 해당 지점에 도달하는 경우의 수

점화식 : 우측, 하단, 우하단 세가지 경우의 수를 활용

Solution

DP의 기초격 문제라 그런가 DP를 조금 맛본 상태에서 접했더니 점화식이 생각났던 얼마안되는 문제

먼저 dp배열을 만들고 해당 dp배열의 상단(우측으로만 진행하는 경우의 수) 하단(아래로만 진행하는 경우의 수)의 값은 도달하는 방법이 한가지 뿐이다. 때문에 먼저 초기화해서 쭉 1로 채워준 후에 해당 값을 가지고 남은 dp배열 모두를 채워나가면 되는데, 점화식은 위에 hint에 적었던 우측, 하단, 우하단 을 받는 이전dp배열을 가져오면 된다.

즉, dp[i][j] = dp[i - 1][j] + dp[i][j-1] + dp[i-1][j-1]; 로 해결이 된다

그림예시

 

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
import java.io.*;
import java.util.*;
 
/**
 * dp 다차원배열 도달할 수 있는 경우의 수
 */
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int n, m;
 
        StringTokenizer st =new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        int[][] dp = new int[1001][1001];
 
        for(int i = 1; i <= n; i++){
            dp[i][1] = 1;
        }
 
        for(int i = 1; i <= m; i++){
            dp[1][i] = 1;
        }
        //값 초기화 끝
 
        for(int i = 2; i <= n; i++){
            for(int j = 2; j <= m; j++){
                dp[i][j] = (((dp[i-1][j] + dp[i][j-1]) % 1000000007) + dp[i-1][j-1]) % 1000000007;
            }
        }
 
        System.out.println(dp[n][m]);
        
    }
}
cs

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 2310번 어드벤처 게임 자바로 풀어 본 짧은 글  (0) 2023.11.28
백준 12755번 수면 장애 자바로 풀어 본 짧은 글  (0) 2023.11.21
백준 1680번 쓰레기 수거 자바로 풀어 본 짧은 글  (0) 2023.09.07
백준 1417번 국회의원 선거 자바로 풀어 본 짧은 글  (0) 2023.08.17
백준 골드5 달성!  (0) 2023.08.11
반응형

1680번 쓰레기 수거

https://www.acmicpc.net/problem/1680

 

1680번: 쓰레기 수거

쓰레기장에서 출발한 쓰레기차가 여러 지점들을 방문하며 쓰레기를 모으고 있다. 쓰레기차는 쓰레기장에서 가까운 지점부터 방문하며, 쓰레기를 모으다가 다음과 같은 경우에 쓰레기장으로 돌

www.acmicpc.net

Comment

일반 시뮬레이션 구현문제라서 평소처럼 풀까하다가 자바스럽게 풀어보고싶어서 객체지향(?)적으로 설계를 하기 위해 노력하면서 구현해보았다.

알고리즘을 풀 때 클래스를 잘 활용하지 않아서 생각보다 많이 오래걸렸던 문제

hint

문제를 잘 읽고 테스트케이스 또한 해당 지문에 맞춰서 잘 이해해야한다.

Solution

메모리나 시간이나 상관없이 구현만 잘하면 되는 문제였다. 때문에 클래스를 만들어서 써보기에 더 좋았던 것 같다.

일단 해당 문제의 1, 2, 3번 조건을 항상 잘 생각해서 염두에 두고 조건을 넣는다면 쉽게 풀리는 문제일 것이다.

1번의 시점은 다음 지점으로 이동하기 전이고, 2번의 시점은 쓰레기를 싣기 전, 3번은 가장 마지막. 이렇게 해당 분기를 잘 확인해서 조건처리만 잘 해준다면 문제 해결은 쉽게 될 것이다.

클래스 활용해서 구현하면 속도가 안나온다....

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import java.io.*;
import java.util.*;
 
public class p1680 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int t = Integer.parseInt(br.readLine());
        int weight, point;
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
 
        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            weight = Integer.parseInt(st.nextToken());
            point = Integer.parseInt(st.nextToken());
            p1680TrashCar garbageTruck = new p1680TrashCar(weight, 0);
 
            for (int i = 0; i < point; i++) {
                st = new StringTokenizer(br.readLine());
                int pointDistance = Integer.parseInt(st.nextToken());   //해당 위치의 거리값(원점기준)
                int pointWeight = Integer.parseInt(st.nextToken());     //해당 위치의 쓰레기양
 
                garbageTruck.movePoint(pointDistance); // 해당 포인트로 이동
 
                while (pointWeight > 0) {
 
                    if (!garbageTruck.possibleCollect(pointWeight)) { //용량을 넘게될때
                        garbageTruck.movePoint(0);
                        garbageTruck.movePoint(pointDistance);
                    }
 
                    if (garbageTruck.possibleCollect(pointWeight)) { // 용량이 넘지않으면 True반환
                        pointWeight = garbageTruck.collectTrash(pointWeight); // 쓰레기 수집 -> 해당 위치의 쓰레기는 0이됨
                    }
 
                    if (garbageTruck.isFull() && i != point - 1) { // 마지막 지점이 아닐 때 쓰레기가 꽉차면 수거장에 가서 비우고 와야함
                        garbageTruck.movePoint(0);
                        garbageTruck.movePoint(pointDistance);
                    }
                }
                if (i == point - 1) {
                    garbageTruck.movePoint(0);
                }
            }
            sb.append(garbageTruck.getMeter()).append("\n");
            System.out.println(garbageTruck.getPoints()); // 쓰레기를 담기위해 문제제출할 땐 주석처리해야함
        }
        System.out.println(sb);
    }
}
 
/**
 * 기본 차 인터페이스
 * recentDestination : 목적지에 이동할 때 이동한 거리를 매 순간 담음
 */
interface p1680Car {
 
    public int getMeter();
 
    public void movePoint(int distance);
 
    ArrayList<Integer> recentDestination = new ArrayList<>();
 
    default public void pointAdd(int n) {
        recentDestination.add(n);
    }
 
    default public ArrayList<Integer> getPoints() {
        return recentDestination;
    }
 
    default public void resetDestList() {
        recentDestination.clear();
    }
 
}
 
/**
 * TrashCar는 p15979Car의 상속을 받아 Meter와 movePoint를 반드시 사용해야한다.
 * 추가로 쓰레기를 담을 capacity, 쓰레기의 용량상태확인이 필요한 trashWeight이 필요
 */
class p1680TrashCar implements p1680Car {
    private int capacity;
    private int trashWeight;
    private int meter;
    private int nowLocation;
 
    public p1680TrashCar(int capacity, int nowLocation) {
        this.capacity = capacity;
        this.nowLocation = nowLocation;
        resetDestList();
    }
 
    @Override
    public int getMeter() {
        return meter;
    }
 
    @Override
    public void movePoint(int point) {
        if (point == 0) {
            pointAdd(nowLocation);
            meter += nowLocation;
            nowLocation = 0;
            trashWeight = 0;
            return;
        }
        pointAdd(point - nowLocation);
        meter += point - nowLocation;
        nowLocation += point - nowLocation;
 
    }
 
    public boolean possibleCollect(int weight) {
        if (capacity < trashWeight + weight) {
            return false;
        }
        return true;
    }
 
    public boolean isFull() { // 비었을 때는 꽉차는지 체크
        if (trashWeight >= capacity) {
            return true;
        }
        return false;
    }
 
    public int collectTrash(int weight) {
        trashWeight += weight;
        return 0;
    }
}
cs
반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 12755번 수면 장애 자바로 풀어 본 짧은 글  (0) 2023.11.21
백준 14494번 다이나믹이 뭐예요? 자바로 풀어 본 짧은 글  (0) 2023.09.15
백준 1417번 국회의원 선거 자바로 풀어 본 짧은 글  (0) 2023.08.17
백준 골드5 달성!  (0) 2023.08.11
백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글  (0) 2023.08.03

+ Recent posts

티스토리툴바