본문 바로가기

공부/알고리즘 문제풀이

[SW Expert Acade] 4616. 점프점프! 개굴이의 점핑!

반응형

4616. 점프점프! 개굴이의 점핑!


SW Expert Academy는 문제의 무단 복제가 금지되어 있기 때문에 링크로 대체하겠습니다!


어떻게 풀까?


동적 계획법에서 가장 중요한 것은 어떠한 규칙으로 점화식을 만들까에 대한 것이죠!

연꽃의 규칙을 발견하는 것이 가장 중요합니다!

연꽃 f1에서 연꽃 f2로 이동하는 경우를 생각해봅시다.

f1에서 f2로 이동하면, 결국 f2에서 f1으로 올 방법은 사라집니다!

왜냐하면, 이동했다는것 자체가 바로 x나 y가 증가했다는 것을 의미하기 때문입니다!

x나 y가 계속해서 증가해야 이동할 수 있는데, 더 작은 f1으로는 이동할 방법이 사라지는 것이죠!





이를 이용해서 연꽃을 한 번 정렬하면, 1번 연꽃부터 n번 연꽃까지 연꽃마다 갈 수 있는 연꽃으로 딱 한번씩만 이동시키면 답이 나오게 됩니다!


그럼 이제 찾아야할 것은 크게 2가지 입니다.


1. 어떤 기준으로 연꽃을 정렬할 것인가?

2. 어떤 방법으로 다음으로 이동할 연꽃을 구할 것인가?


우선 어떤 기준으로 연꽃을 정렬할지 생각해 봅시다!


결국 연꽃은 맨 왼쪽 위를 (0,0)으로 보았을 때, 오른쪽이나 아래쪽으로만 점프를 할 수 있는 것을 알 수 있습니다.

그렇다면, 연꽃의 x의 크기가 작은 순서에 따라 정렬하고, 만약 x의 값이 같다면 y의 크기가 작은 것이 앞으로 오도록 정렬한 다음에, 순서대로 보면 어떨까요?


그렇게 현재 처리하는 연꽃은 앞에서 처리했던 연꽃으로 이동할 방법이 전혀 없기 때문에 저희가 원했던 결과대로 동작하는 것을 볼 수 있습니다!


그림을 통해 확인해 봅시다.


우선, 맨 왼쪽 위에있는 f1에서 시작합니다. f1은 f4, f2, f3로 이동할 수 있습니다.


f2에서는 f3와 f6로 이동할 수 있습니다.



f3에서는 이동할 연꽃이 없습니다.


f4에서는 f5로 이동할 수 있습니다.

f5에서도 이동할 곳이 없습니다.


f6는 저희가 찾던 6번 연꽃이고, 경로는 f1->f2->f6 하나군요!


이 방법에서 주목할 부분은 f3 입니다.

경로가 f1->f3로 바로 오는 방법과

f1->f2->f3로 오는 경로 2가지 입니다!


이 경우에는 어떻게 처리하는것이 좋을까요?


문제를 조금 생각해보면, 가장 많은 에너지를 얻기 위해서는 f3에 도착했을 때 가장 많은 에너지를 가지고 있는것이 정답입니다.

따라서, f2에서 f3로 가는 경로를 처리할때, 저희는 아래와 같은 식을 사용할 수 있습니다.



ernerge는 해당 연꽃에 도착할 때의 최대 에너지이고, fly는 그 연꽃에 있는 파리의 수 입니다.

그리고, energe(a)에서는 energe(b)로 점프할 수 있다고 가정하겠습니다!


이렇게 에너지를 구하면, 마지막에는 n번 연꽃의 에너지가 몇인지만 알려주면 그것이 바로 답이 될 것입니다.


그리고 안한 것이 있는데... 해당 연꽃에서의 최대 에너지가 k보다 작다면, 점프를 할 수 없다는 조건을 추가하셔야 합니다!




그럼이제 다음 문제로 넘어가봅시다. 어떻게하면 한 연꽃에서 다음 연꽃으로 점프할 수 있다는 것을 만들 수 있을까요?


점프할 때마다 연꽃들을 보면서 자기보다 x값은 같으면서 y값은 큰 값을 찾거나 y값은 같으면서 x값을 큰 연꽃을 찾는 것은 굉장히 비효율적인것 처럼 보입니다!



위 그림처럼 x 좌표와 y좌표를 인덱스로 하는 배열 2개가 있다고 생각합시다!

주황색과 초록색은 서로 다른 배열입니다.

그리고 fa의 위치가 입력될 때마다 해당 x좌표와 y좌표에 맞게 배열에 넣으면, 아래와 같은 모습이 될 것입니다.


예를 들면, f1은 (3,1)이기 때문에 초록색 배열의 3번 인덱스와 주황색 배열의 1번 인덱스에 f1이 들어가게 될 것입니다.


이제 이 배열을 처음에 연꽃을 정렬하듯이 정렬하면 아래의 그림과 같아집니다!




오오, 이제 해당 연꽃이 초록색 배열에서는 몇번째 인덱스인지, 주황색 배열에서는 몇번째 인덱스인지만 알면 다음에 갈 수 있는 연꽃의 번호를 쉽게 알 수 있습니다!


자신의 인덱스 다음번호부터 끝까지가 바로 다음으로 이동할 수 있는 연꽃이기 때문입니다!


예를들면, f1같은 경우는 다음으로 갈 수 있는 연꽃이 f3과 f6 이겠군요!

f3은 갈 수 있는 연꽃이 없을 겁니다.


x좌표와 y좌표의 끝도 10만까지이기 때문에 vector를 이용하면 메모리에서도 문제가 없을 것 같습니다!



코드


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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#pragma once
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
struct YEON
{
    int pos[2], f;
} yeons[300000];
 
//move[x,y][좌표] : 다음 연꽃으로 점프하기 위해 정렬하는곳
vector<int> moves[2][100001];
int temp[300000], sIdx[2][300000];// sidx[x,y][연꽃번호] : 연꽃이 x좌표나 y좌표에서 몇 번째에 있는지 저장한다.
int maxF[300000]; // 현재 연꽃에서 가장 많은 에너지를 저장한다.
int yeonorder[300000],ytemp[300000]; // 연꽃을 정렬한 정보를 저장한다.
int n,k;
 
//x의 값이 작은 것이 앞으로 와야한다.
//x의 값이 같으면 y의 값이 작은 것이 앞으로 와야한다.
bool comp(int i1, int i2) {
    if (yeons[i1].pos[0< yeons[i2].pos[0]) {
        return true;
    }
    else if (yeons[i1].pos[0== yeons[i2].pos[0])
    {
        return yeons[i1].pos[1< yeons[i2].pos[1];
    }
    else
    {
        return false;
    }
}
 
void yeonSort(int left, int m, int right)
{
    int l = left, r = m + 1, k = l;
    while (l <= m && r <= right)
    {
        if (comp(yeonorder[l], yeonorder[r])) {
            ytemp[k++= yeonorder[l++];
        }
        else {
            ytemp[k++= yeonorder[r++];
        }
    }
 
    while (l <= m) ytemp[k++= yeonorder[l++];
    while (r <= right) ytemp[k++= yeonorder[r++];
 
    for (int i = left; i <= right; i++) yeonorder[i] = ytemp[i];
}
 
//전체 연꽃을 정렬하는 부분.
void yeonmerge(int l, int r)
{
    if (l < r)
    {
        int m = (l + r) / 2;
        yeonmerge(l, m);
        yeonmerge(m + 1, r);
        yeonSort(l, m, r);
    }
}
 
 
void mergeSort(vector<int>& arr, int left, int right, int m, int flag)
{
    int l = left, k = left, r = m + 1;
 
    while (l <= m && r <= right)
    {
        if (yeons[arr[l]].pos[flag] < yeons[arr[r]].pos[flag]) temp[k++= arr[l++];
        else
        {
            temp[k++= arr[r++];
        }
    }
 
    while (l <= m) temp[k++= arr[l++];
    while (r <= right) temp[k++= arr[r++];
 
    for (int i = left; i <= right; i++)
    {
        //sIdx : 자신이 해당 좌표에서 몇번째인지 저장한다.
        arr[i] = temp[i];
        sIdx[flag ^ 1][temp[i]] = i;
    }
}
 
//다음 연꽃을 뛸 수 있도록 정렬하는 곳 flag의 이유는 x에서 점프하는 경우에는 y를 기준으로 정렬해야하기 때문이다!
void merge(vector<int>& arr, int left, int right, int flag)
{
 
    if (left < right)
    {
        int m = (left + right) / 2;
 
        merge(arr, left, m, flag);
        merge(arr, m + 1, right, flag);
        mergeSort(arr, left, right, m, flag);
    }
}
 
int max(int i1, int i2)
{
    return i1 > i2 ? i1 : i2;
}
 
int main()
{
    int t;
    scanf("%d\n"&t);
 
    for (int tc = 1; tc <= t; tc++)
    {
        memset(maxF, -1sizeof(maxF));
        scanf("%d %d\n"&n, &k);
 
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 100001; j++)
            {
                moves[i][j].clear();
            }
        }
 
        for (int i = 0; i < n; i++)
        {
            scanf("%d %d %d\n"&yeons[i].pos[0], &yeons[i].pos[1], &yeons[i].f);
            moves[0][yeons[i].pos[0]].push_back(i);
            moves[1][yeons[i].pos[1]].push_back(i);
        }
 
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 100001; j++)
            {
                //x 좌표에 대한 이동이라면, y 좌표를 기준으로 정렬해야한다.
                merge(moves[i][j], 0, moves[i][j].size() - 1, i^1);
            }
        }
 
        for (int i = 0; i < n; i++) yeonorder[i] = i;
 
        yeonmerge(0, n - 1);
        maxF[0= yeons[0].f;
 
        for (int i = 0; i < n; i++) {
            int now = yeonorder[i];
 
            // n 번 연꽃까지만 확인하면 된다.
            if (now == n - 1break;
 
            //점프를 할 수 없다.
            if (maxF[now] < k) continue;
            //점프를 위해서 에너지를 소비해야한다.
            maxF[now] -= k;
 
            for (int j = 0; j < 2; j++) {
                for (int idx = sIdx[j][now] + 1; idx < moves[j][yeons[now].pos[j]].size(); idx++) {
                    int next = moves[j][yeons[now].pos[j]][idx];
                    //최대 에너지를 수정한다.
                    maxF[next] = max(maxF[next], maxF[now] + yeons[next].f);
                }
            }
        }
        //n번 연꽃의 최대 에너지를 출력한다.
        printf("#%d %d\n", tc, maxF[n-1]);
    }
    return 0;
}
cs


여담

시간 복잡도는 어떻게 될까요??

시간복잡도가 굉장히 해결하기 난해한 것 같습니다..

왜냐하면, (1,1)부터 (1,100000)까지 일렬로 나열되어 있으면, 결국까지도 나오기 때문입니다.

다만, 이런 경우는 극히 드물기 때문에 테스트 케이스에서도 이러한 경우는 빠진 것 같습니다.


 



반응형