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

 

1 ~ N번 방은 서로 원형으로 연결되어 있으며, 각 방에는 Ci개의 쪽방이 있을 수 있습니다.

통로로 직접 연결되어 있는 두 방에는 하나의 개미만 들어갈 수 있으며, 개미굴에 살고있는 개미의 최대 수를 구하는 문제입니다.

 

문제의 카테고리가 dp와 그리디가 있었지만 저는 그리디로 해결했습니다.

우선 쪽방이 있다면 무조건 들어가는 것이 이득입니다.

쪽방은 i번 방의 바로 아래에 있는 자식 노드기 때문에 쪽방의 갯수를 세어주도록 합니다.

 

그 다음은 쪽방이 없는 나머지 방을 세어줍니다.

나머지 방에는 연속된 방으로 세어주시고, (연속된 방의 갯수 (cnt) + 1) / 2으로 구할 수 있습니다.

 

그것들을 정답에 더해주시면 되는데 마지막으로 생각할게 개미굴은 원형으로 되어있기 때문에 1번과 N번 방이 서로 연결되어 있습니다.

순회를 1번 방부터 했기 때문에 만약 1번과 N번 방 둘다 쪽방이 없다면 연속된 방의 갯수들을 합쳐줘야 합니다. (cnt + tmp)

그걸 위해서 처음에 1번 방부터 isFirst 변수를 추가하여 처음 연속된 빈방의 갯수를 tmp에 저장해두었습니다.

 

 

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
#include <iostream>
#define MAX 250001
using namespace std;
typedef long long ll;
 
ll list[MAX];
bool flag;
int N;
 
void func() {
    if (!flag) {
        cout << (N >> 1) << '\n';
        return;
    }
 
    ll ret = 0;
    ll cnt = 0;
    ll tmp = 0;
    bool isFirst = true;
    for (int i = 0; i < N; i++) {        
        if (!list[i]) cnt++;
        else {
            if (isFirst) tmp = cnt;
            ret += list[i];
            isFirst = false;
            ret += ((cnt + 1LL) >> 1);
            cnt = 0;
        }
    }
 
    if (!list[0] && !list[N - 1]) {
        ret -= ((tmp + 1LL) >> 1);
        ret += ((tmp + cnt + 1LL) >> 1);
    }
    else ret += ((cnt + 1LL) >> 1);
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
        flag |= list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > Greedy' 카테고리의 다른 글

boj 14464 소가 길을 건너간 이유 4  (0) 2024.07.05
boj 1263 시간 관리  (0) 2024.07.03
boj 18185 라면 사기 (Small)  (0) 2024.07.02
boj 16120 PPAP  (0) 2021.10.16
boj 2262 토너먼트 만들기  (0) 2021.10.16

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

 

소는 A ~ B 시간 사이에만 이동할 수 있고, 닭은 T 시간에만 도움을 줄 수 있습니다.

즉 A <= T <= B 가 되어야 닭이 소를 도와줄 수 있습니다.

 

구현은 간단합니다.

가장 빠르게 도움을 줄 수 있는 닭을 찾기 위해 닭은 오름차순으로 정렬합니다.

그리고 소는 끝시간 기준 오름차순으로 정렬합니다.

이후에는 소 한마리씩 순회하여 도움을 받을 적절한 닭을 찾아주시면 됩니다.

 

범위가 각각 2만이기 때문에 TLE가 나오지 않을까 생각했지만 N * M으로도 풀리는 문제였습니다.

아마 중간에 적절한 답을 찾으면 break를 해주면서 시간이 어느정도 단축되는 것으로 보입니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 20001
using namespace std;
typedef pair<int, int> pii;
 
int list[MAX];
pii cow[MAX];
int N, M;
 
void func() {
    sort(list, list + N);
    sort(cow, cow + M, [](pii a, pii b) {
        return a.second < b.second;
    });
 
    int ret = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (list[j] == -1) continue;
            if (cow[i].first > list[j] || list[j] > cow[i].second) continue;
 
            ret++;
            list[j] = -1;
            break;
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
 
    for (int i = 0; i < M; i++) {
        cin >> cow[i].first >> cow[i].second;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > Greedy' 카테고리의 다른 글

boj 28325 호숫가의 개미굴  (0) 2024.07.06
boj 1263 시간 관리  (0) 2024.07.03
boj 18185 라면 사기 (Small)  (0) 2024.07.02
boj 16120 PPAP  (0) 2021.10.16
boj 2262 토너먼트 만들기  (0) 2021.10.16

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

 

1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000 ...

위 동전들을 적절히 사용하여 N을 만들기 위한 최소 갯수를 구하는 문제입니다.

 

동전들을 3개씩 끊어본다면

(1, 10, 25)

(1, 10, 25) * 100

(1, 10, 25) * 100 * 100

(1, 10, 25) * 100 * 100 * 100

이런식으로 규칙이 된다는 것을 알 수 있습니다.

그러면 굳이 문제에서 요구하는 큰 범위까지 갈 필요 없이 100 단위로 끊어서 접근한다면 간단하게 해결할 수 있습니다.

 

같은 금액에서의 답은 똑같기 때문에 dp를 사용했습니다.

그리고 dp 배열을 초기화할 필요도 없습니다.

(1, 10, 25) 으로 99원을 만들든, (100, 1000, 2500) 으로 9900원을 만들든 똑같은 결과가 나오기 때문입니다.

여기까지 오셨다면 구현은 간단합니다.

 

 

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
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 101
using namespace std;
typedef long long ll;
 
int dp[MAX];
int list[3] = { 1,10,25 };
ll N;
 
int solve(int n) {
    if (!n) return 0;
 
    int& ret = dp[n];
    if (ret != -1) return ret;
 
    ret = 1e9;
    for (int i = 0; i < 3; i++) {
        if (n < list[i]) continue;
 
        ret = min(ret, solve(n - list[i]) + 1);
    }
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    
    int ret = 0;
    while (N) {
        ret += solve(N % 100LL);
        N /= 100LL;
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 1229 육각수  (0) 2024.06.30
boj 25378 조약돌  (0) 2024.06.29
boj 2216 문자열과 점수  (0) 2024.06.28
boj 1354 무한 수열 2  (0) 2024.06.27
boj 3114 사과와 바나나  (0) 2024.06.13

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

 

문제를 보자마자 6068번 시간 관리하기 문제랑 같다는 것을 느꼈습니다.

마감 시간(Si)과 일을 하는데 걸리는 시간(Ti)이 주어지고, 언제부터 시작하면 일을 끝낼 수 있는지 구해야 합니다.

마감 시간 기준 내림차순으로 정렬하여 뒤에서부터 탐색한다면 쉽게 해결할 수 있습니다.

저는 혹시 몰라서 Si가 같다면 Ti 기준으로도 정렬을 했지만 생각해보니 그럴 필요는 없어보입니다.

 

시간을 최대로 세팅을 먼저 하고, 내려가면서 Ti를 빼주시면 되겠습니다.

도중에 현재 작업의 Si보다 t가 더 크다면 Si로 현재 시간을 조정해주시면서 진행해주시면 됩니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 1001
using namespace std;
typedef pair<int, int> pii;
 
pii list[MAX];
int N;
 
bool cmp(pii a, pii b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}
 
void func() {
    sort(list, list + N, cmp);
 
    int t = 1e9;
    for (int i = 0; i < N; i++) {
        t = min(t, list[i].second);
        t -= list[i].first;
 
        if (t < 0) {
            cout << "-1\n";
            return;
        }
    }
 
    cout << t << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > Greedy' 카테고리의 다른 글

boj 28325 호숫가의 개미굴  (0) 2024.07.06
boj 14464 소가 길을 건너간 이유 4  (0) 2024.07.05
boj 18185 라면 사기 (Small)  (0) 2024.07.02
boj 16120 PPAP  (0) 2021.10.16
boj 2262 토너먼트 만들기  (0) 2021.10.16

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

 

다이아 문제중에 해볼만한 문제로 가져와봤습니다.

 

1. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.
2. i번 공장과 (i + 1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N - 1). 이 경우 비용은 5원이 든다.
3. i번 공장과 (i + 1)번 공장, (i + 2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N - 2). 이 경우 비용은 7원이 든다.

우선 라면을 구매할 수 있는 방법은 이렇게 3가지입니다.

 

i번째 공장에서는 남아있는 모든 라면을 구매하는게 맞겠고,

i + 1, i + 2번째 공장의 라면을 가능하면 추가로 구매하는게 더 좋습니다.

제가 구현한 방식은 i번째 라면은 개당 3원씩 모두 구매하고, i + 1, i + 2번째 라면을 구매할때마다 2원을 추가하는 방식으로 구현했습니다.

 

하지만 i ~ i + 2 범위 내에 가능한 모든 라면을 구매한다면 반례가 존재합니다.

4
1 2 1 1

여기서 가능한대로 모든 라면을 구매한다고 했을 때 1 ~ 3번째 공장에서 라면을 구매했을 것입니다. (소모한 금액: 7)

0 1 0 1

그러면 남은 라면은 이렇게 될 것이고, 남은 공장에서 하나씩 구매한다면 7 + 3 + 3 = 13의 금액이 필요합니다.

 

 

하지만 처음에 3번 공장에서 구매하지 않는다면

0 1 1 1

1, 2번째 공장에서만 라면을 구입하고, (소모한 금액: 5)

나머지 2 ~ 4번째 공장에서 라면을 구입한다면 5 + 7 = 12의 금액이 필요하여 이게 최소가 됩니다.

 

따라서 하나더 고려해야할 부분은 최초 필요한 갯수가 list[i + 1] > list[i + 2] 이라면

"i + 1번째 공장에서 남긴 수만큼 i + 2번째 공장에서도 남겨야 한다"가 됩니다.

물론 i + 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
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <algorithm>
#define MAX 10010
using namespace std;
 
int list[MAX];
int N;
 
void func() {
    int ret = 0;
    for (int i = 0; i < N; i++) {
        if (!list[i]) continue;
        int cnt = list[i];
        list[i] = 0;
        ret += (3 * cnt);
 
        if (i + 1 >= N) continue;
        cnt = min(cnt, list[i + 1]);
        list[i + 1] -= cnt;
        ret += (2 * cnt);
 
        if (i + 2 >= N) continue;
        if (cnt + list[i + 1] > list[i + 2]) {
            cnt = min(cnt, max(0, list[i + 2] - list[i + 1]));
        }
        list[i + 2] -= cnt;
        ret += (2 * cnt);
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > Greedy' 카테고리의 다른 글

boj 14464 소가 길을 건너간 이유 4  (0) 2024.07.05
boj 1263 시간 관리  (0) 2024.07.03
boj 16120 PPAP  (0) 2021.10.16
boj 2262 토너먼트 만들기  (0) 2021.10.16
boj 13904 과제  (0) 2021.09.30

RealMySQL 2권 스터디

작년 3월에 1권 스터디로 시작했고, 휴식기간 2달을 포함해서도 1년이 넘는 장기간에 걸쳐서 2권 스터디까지 마무리되었다.

생각보다 딥한 내용이 많았어서 완벽하게 이해하고 넘어가겠다 라기보단 이런게 있다 정도로 읽고 넘어가자는 마인드로 했다.

이번달 내용 중에는 슬로우 쿼리, 미사용 인덱스, 테이블의 작업량 등 이런 세세한 것들을 조회하여 최적화에 도움될 수 있겠다는 생각이 들었고,

생각보다 유용한데 모르고 있는 신기한 기능들이 많았고, 언제 이런것들을 써볼까 하고 관심있게 본 내용들이 많았다.

물론 기억나는건 많진 않다 ^^ 이건 여유를 갖고 복습해야 하지 않을까 싶다.

 

1일 1알고리즘

 

마무리

같이 부트캠프 했던 분들이랑 모각코를 시작했다.

처음에는 오후 9시부터 자기 전까지 진행했었고, 지금은 오전 9시부터 자기 전까지로 변경하여 진행하고 있다.

그래도 같이 공부하는 분들이 있어서 나도 자극받고 할 수 있을 것 같다.

SQL 문제도 풀고있고, CS 공부도 계속 하고있는데 CS는 해도해도 끝이 안나오는것 같다.

그래서인지 이번 회고글을 되게 빠르게 쓰는 느낌인데 사람이 부지런해야지 ^^

 

아 그리고 현대모비스 알고리즘 대회 예선을 했는데 다신 안나가려고 ^^

작년과 마찬가지로 0솔로 마무리했다. 아니 탈주가 맞는듯

반례를 1시간 반만에 찾았지만 내가 생각한 개념이 아니다 라는 결론이 나왔고 그대로 탈주했다.

얘기를 들어보니 빡구현이 많았다는 소문이 들리긴 하지만 어우 다음 대회는 이거보단 낫겠지 라는 회로를 돌려봐야겠다.

'잡담' 카테고리의 다른 글

Nexters 24기 회고  (2) 2024.06.16
5월 회고  (1) 2024.06.07
4월 회고  (2) 2024.05.13
3월 회고  (0) 2024.04.13
2월 회고  (4) 2024.03.07

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

 

간단한 dp 문제입니다.

문제가 요구하는 육각수들의 수를 미리 구한 다음 N을 만들기 위해 필요한 육각수의 갯수를 구하여 해결할 수 있습니다.

 

육각수의 수는

1 * 1

2 * 3

3 * 5

4 * 7

5 * 9

이렇게 규칙을 찾을 수 있고, An = n * (2n - 1) 으로 구할 수 있습니다.

 

dp[i] = i를 만들기 위해 필요한 육각수의 최소 갯수

인덱스가 갯수이므로 dp[i] = dp[i - 현재 육각수의 갯수] + 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
38
39
40
41
42
43
#include <iostream>
#define MAX_N 1000001
#define MAX_M 710
using namespace std;
 
int list[MAX_M];
int dp[MAX_N];
int N;
 
void init() {
    for (int i = 1; i < MAX_M; i++) {
        list[i] = i * ((i << 1) - 1);
    }
}
 
void func() {
    init();
 
    dp[1] = 1;
    for (int i = 2; i <= N; i++) {
        dp[i] = 1e9;
        for (int j = 1; j < MAX_M; j++) {
            if (i < list[j]) break;
            dp[i] = min(dp[i], dp[i - list[j]] + 1);
        }
    }
 
    cout << dp[N] << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 1398 동전 문제  (0) 2024.07.04
boj 25378 조약돌  (0) 2024.06.29
boj 2216 문자열과 점수  (0) 2024.06.28
boj 1354 무한 수열 2  (0) 2024.06.27
boj 3114 사과와 바나나  (0) 2024.06.13

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

 

1. 인접한 두 장소에서 임의의 동일한 개수의 조약돌을 가져가기
2. 한 장소에서 임의의 개수의 조약돌을 가져가기

조약돌을 가져갈 수 있는 방법은 이렇게 두가지 입니다.

 

"어떤 장소에 조약돌이 더 이상 없는 경우에도 그 장소는 그대로 남아 있어서, 초기에 인접하지 않았던 두 장소가 인접한 것으로 바뀌지 않는다."

그리고 이렇게 조건도 명시되어 있어서 그 자리에 있는 조약돌은 모두 가져가야 되는것을 알 수 있습니다.

 

dp[i]: i번 위치까지 1번 작업을 통해 줄어든 작업의 최대 횟수

우선 최대 작업 횟수는 N번으로,  모두 2번 방법으로 가져가는 경우입니다.

dp를 구할때는 1번 방법만 사용하기 때문에 앞에서 가져간 이후 몇개가 남았는지 유지하는게 중요합니다.

도중에 r = 0이 되었다면 dp[i - 1] + 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
38
39
40
#include <iostream>
#include <algorithm>
#define MAX 2501
using namespace std;
 
int dp[MAX];
int list[MAX];
int N;
 
void func() {
    for (int i = 1; i <= N; i++) {
        dp[i] = max(dp[i], dp[i - 1]);
        int r = list[i];
        for (int j = i + 1; j <= N; j++) {
            r = list[j] - r;
 
            if (r < 0) break;
            if (!r) dp[j] = max(dp[j], dp[i - 1] + 1);
        }
    }
 
    cout << N - dp[N] << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 1398 동전 문제  (0) 2024.07.04
boj 1229 육각수  (0) 2024.06.30
boj 2216 문자열과 점수  (0) 2024.06.28
boj 1354 무한 수열 2  (0) 2024.06.27
boj 3114 사과와 바나나  (0) 2024.06.13

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

 

같은 위치에 있는 문자를 비교하여 아래와 같이 점수를 받습니다.

1. 두 문자가 같은 경우에는 A(> 0)점을 받게 된다. 단, 두 문자가 모두 공백인 경우는 허용되지 않는다.
2. 두 문자 중 적어도 하나가 공백인 경우에는 B(< 0)점을 받게 된다.
3. 두 문자가 모두 공백이 아니고 서로 다른 경우에는 C(< 0)점을 받게 된다.

 

여기서 문자 사이에 공백을 원하는대로 넣을수 있기 때문에

적절하게 공백을 넣어서 점수를 최대로 받아야 하는 문제입니다.

 

dp[idx1][idx2]: 문자열을 idx1, idx2까지 사용했을 때 얻을 수 있는 최대 점수

s1, s2 중 하나의 문자에 공백을 추가하거나 두 문자를 비교하여 a, b, c 중 적절한 값을 더합니다.

위 3가지 중 max를 구하도록 합니다.

 

 

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
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#define MAX 3010
using namespace std;
 
string s1, s2;
int dp[MAX][MAX];
int a, b, c;
int len1, len2;
 
int solve(int idx1, int idx2) {
    if (idx1 == len1) return (len2 - idx2) * b;
    if (idx2 == len2) return (len1 - idx1) * b;
 
    int& ret = dp[idx1][idx2];
    if (ret != -1) return ret;
    ret = b + max(solve(idx1 + 1, idx2), solve(idx1, idx2 + 1));
    if (s1[idx1] == s2[idx2]) {
        ret = max(ret, solve(idx1 + 1, idx2 + 1) + a);
    }
    else {
        ret = max(ret, solve(idx1 + 1, idx2 + 1) + c);
    }
 
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    cout << solve(0, 0) << '\n';
}
 
void input() {
    cin >> a >> b >> c >> s1 >> s2;
    len1 = s1.size();
    len2 = s2.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 1229 육각수  (0) 2024.06.30
boj 25378 조약돌  (0) 2024.06.29
boj 1354 무한 수열 2  (0) 2024.06.27
boj 3114 사과와 바나나  (0) 2024.06.13
boj 11560 다항식 게임  (0) 2024.06.13

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

 

  • Ai = 1 (i ≤ 0)
  • Ai = A⌊i / P⌋ - X + A⌊i / Q⌋ - Y (i ≥ 1)

여기에서 An을 구하는 문제입니다.

우선 N이 10^13이기 때문에 단순 배열만으로는 해결할 수 없습니다.

그래서 처음 생각해낸건 map을 사용하여 dp를 해결하려고 했습니다.

 

dp 재귀를 돌릴 때 dp[n] != -1이면 dp[n]을 리턴했던것 처럼

map에 포함되어 있는 수는 이미 방문처리가 되었으므로 그 수를 리턴하도록 합니다.

 

 

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
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
 
unordered_map<ll, ll> m;
ll N, p, q, x, y;
 
ll solve(ll n) {
    if (n <= 0) return 1LL;
    if (m.find(n) != m.end()) return m[n];
    return m[n] = solve(n / p - x) + solve(n / q - y);
}
 
void func() {
    cout << solve(N) << '\n';
}
 
void input() {
    cin >> N >> p >> q >> x >> y;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

 

근데 생각보다 메모리를 많이 차지하고, 시간도 많이 소요되는 것을 알 수 있습니다.

다른분들의 제출 현황을 보니 이 방법은 비효율적이라는 것을 알 수 있었습니다.

 

제가 확인해봤던 풀이로는 배열을 활용하는 방법이었습니다.

하지만 N의 범위가 10^13이기 때문에 모든 범위를 배열로 해결할 수는 없습니다.

문제에서 허용하는 메모리 512MB 내에서는 가능하기 때문에 10000000 까지는 배열로, 나머지는 재귀로 해결할 수 있었습니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 10000001
using namespace std;
typedef long long ll;
 
ll dp[MAX];
ll N, p, q, x, y;
 
ll solve(ll n) {
    if (n < MAX) return dp[n];
 
    ll l = 1LL;
    if (n / p - x > 0) l = solve(n / p - x);
 
    ll r = 1LL;
    if (n / q - y > 0) r = solve(n / q - y);
 
    return l + r;
}
 
void init() {
    dp[0] = 1LL;
    for (int i = 1; i < MAX; i++) {
        dp[i] = dp[max(0LL, i / p - x)] + dp[max(0LL, i / q - y)];
    }
}
 
void func() {
    init();
    cout << solve(N) << '\n';
}
 
void input() {
    cin >> N >> p >> q >> x >> y;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

 

아까와 비교하면 메모리와 시간 차이가 정말 많이 난다는 것을 알 수 있습니다.

'algorithm > dp' 카테고리의 다른 글

boj 25378 조약돌  (0) 2024.06.29
boj 2216 문자열과 점수  (0) 2024.06.28
boj 3114 사과와 바나나  (0) 2024.06.13
boj 11560 다항식 게임  (0) 2024.06.13
boj 28018 시간이 겹칠까?  (0) 2023.08.08

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

 

이 문제에서 고려할 부분은 cost를 적절하게 소모하여 1번 방에서 N번 방까지 이동시켜야 합니다.

각 방마다 type이 3개가 있기 때문에 어떤 방에서 cost가 소모되는지, 추가되는지, 유지되는지를 확인해야 합니다.

 

type == E이면 빈 방이며, cost가 들지 않습니다.

type == L이면 레프리콘 방으로, 현재 cost, 이동할 방의 cost 중 높은 값을 갖게 됩니다.

type == T이면 트롤 방으로, 해당 방의 cost만큼 소모해야 합니다. 더 적은 금액을 갖고있다면 지나갈 수 없습니다.

여기서 E 방은 cost가 0인 L방으로 취급이 가능합니다.

따라서 저는 L, T 2가지 경우만 고려했습니다.

 

전체적인 로직으로는 1번 방부터 출발하여 연결되어 있는 모든 방을 bfs로 탐색합니다.

나머지는 위에 작성한 것들을 참고하여 다음 방으로 이동하면 됩니다.

cost마다 어떤 방을 갈 수 있거나 못 가는 경우가 나뉘기 때문에 visit 배열을 2차원 배열로 사용하여 방문처리를 다르게 했습니다.

 

"이는 맨 처음에 모험가가 1번 방에서 시작하려 할 때에도 마찬가지이다."

라는 말이 문제에 명시되어 있어서 1번 방부터 cost를 검사해야 합니다.

1번 방에서는 금액이 0이기 때문에 T번 방이고 cost가 있다면 false를 리턴해주도록 하고,

나머지의 경우에는 해당 방의 cost만큼의 금액을 더하여 출발해주시면 되겠습니다.

 

 

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
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#define MAX_N 1001
#define MAX_COST 501
using namespace std;
typedef pair<int, int> pii;
 
typedef struct Node {
    char type;
    int cost;
    vector<int> next;
}Node;
 
Node list[MAX_N];
bool visit[MAX_N][MAX_COST];
int N;
 
bool bfs(int s) {
    queue<pii> q;
    if (list[s].type == 'T' && list[s].cost) return false;
    else {
        q.push({ s,list[s].cost });
        visit[s][list[s].cost] = true;
    }
 
    while (!q.empty()) {
        int x = q.front().first;
        int cost = q.front().second;
        q.pop();
 
        if (x == N) return true;
 
        for (auto next : list[x].next) {
            if (list[next].type == 'T') {
                if (cost < list[next].cost) continue;
                if (visit[next][cost - list[next].cost]) continue;
                q.push({ next, cost - list[next].cost });
                visit[next][cost - list[next].cost] = true;
            }
            else {
                if (visit[next][max(cost, list[next].cost)]) continue;
                q.push({ next, max(cost, list[next].cost) });
                visit[next][max(cost, list[next].cost)] = true;
            }
        }
    }
 
    return false;
}
 
void func() {
    if (bfs(1)) cout << "Yes\n";
    else cout << "No\n";
}
 
void input() {
    cin >> N;
    if (!N) exit(0);
 
    int x;
    for (int i = 1; i <= N; i++) {
        cin >> list[i].type >> list[i].cost;
        while (1) {
            cin >> x;
            if (!x) break;
            list[i].next.push_back(x);
        }
    }
}
 
void init() {
    memset(visit, false, sizeof(visit));
    for (int i = 1; i <= N; i++) {
        list[i].next.clear();
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    while (1) {
        input();
        func();
        init();
    }
 
    return 0;
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 2412 암벽 등반  (0) 2024.06.22
boj 14497 주난의 난(難)  (0) 2024.06.21
boj 2132 나무 위의 벌레  (0) 2024.06.17
boj 16985 Maaaaaaaaaze  (0) 2022.12.16
boj 14466 소가 길을 건너간 이유 6  (1) 2022.10.13

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

 

(0, 0) 좌표에서 출발하여 주어진 좌표만을 이용해서 목적지인 y = E에 도착하는 최소 이동횟수를 구하는 문제입니다.

좌표 범위가 x * y = 1000000 * 200000 이라 배열로는 해결할 수 없습니다.

그래서 홈이 있는 좌표는 set으로 관리하도록 합니다.

set에는 같은 y좌표들 기준으로 x 좌표를 모아주시면 됩니다. (목적지가 y=E이라 y 좌표 기준)

 

이동은 x, y 각각 -2 ~ +2 범위 내에서만 이동이 가능하고, 범위 내에 홈이 있다면 해당 홈을 지우고 queue에 넣어주시면 됩니다.

일반적으로 bfs는 visit 배열을 사용하여 방문처리를 하지만 범위가 너무 크기 때문에 set에 있는 원소를 지우는 방식으로 방문처리를 대신할 수 있습니다.

 

 

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
#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
#define MAX 200001
using namespace std;
typedef pair<int, int> pii;
 
set<int> s[MAX];
int N, E;
 
int bfs(int sx, int sy) {
    queue<pii> q;
    q.push({ sx,sy });
    for (int t = 0; !q.empty(); t++) {
        int qsize = q.size();
        while (qsize--) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            if (y == E) return t;
 
            for (int ny = max(0, y - 2); ny <= min(E, y + 2); ny++) {
                for (int nx = max(0, x - 2); nx <= x + 2; nx++) {
                    if (s[ny].find(nx) == s[ny].end()) continue;
                    q.push({ nx,ny });
                    s[ny].erase(nx);
                }
            }
        }
    }
 
    return -1;
}
 
void func() {
    cout << bfs(0, 0) << '\n';
}
 
void input() {
    int x, y;
    cin >> N >> E;
    for (int i = 0; i < N; i++) {
        cin >> x >> y;
        s[y].insert(x);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 2310 어드벤처 게임  (0) 2024.06.25
boj 14497 주난의 난(難)  (0) 2024.06.21
boj 2132 나무 위의 벌레  (0) 2024.06.17
boj 16985 Maaaaaaaaaze  (0) 2022.12.16
boj 14466 소가 길을 건너간 이유 6  (1) 2022.10.13

+ Recent posts

티스토리툴바