# Link

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

 

2616번: 소형기관차

첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있

www.acmicpc.net

 

 

# Code - C++

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'
#define len(x) (int)(x).length()
#define size(x) (int)(x).size()
#define str(x) to_string(x)
#define error logic_error("line " + str(__LINE__))

// Set up : Definitions
const int MAX = 50'000;

// Set up : Global Variables
int N, M;
int A[MAX+1];
int PS[MAX+1];
int dp[MAX+1][3+1];

// Set up : Functions Declaration
int f(int idx, int cnt);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N;
    for (int i=1; i<=N; i++)
        cin >> A[i];
    cin >> M;

    // Process
    memset(dp, -1, sizeof(dp));
    for (int i=1; i<=N; i++) {
        PS[i] = A[i] + PS[i-1];
    }

    int ans = f(N, 3);

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
int f(int idx, int cnt)
{
    if (cnt == 0 || idx < M) return 0;
    if (dp[idx][cnt] != -1) return dp[idx][cnt];

    int tmp1 = f(idx-1, cnt);
    int tmp2 = f(idx-M, cnt-1) + (PS[idx] - PS[idx-M]);

    return dp[idx][cnt] = max(tmp1, tmp2);
}

 

 

지적, 조언, 첨언 모두 환영합니다!!!
저작자표시 비영리 변경금지 (새창열림)

'Problem Solving > 백준' 카테고리의 다른 글

[ Problem Solving :: 백준 ] 2698 / 인접한 비트의 개수  (0) 2021.11.16
[ Problem Solving :: 백준 ] 14606 / 피자 (Small)  (0) 2021.11.16
[ Problem Solving :: 백준 ] 2602 / 돌다리 건너기  (0) 2021.11.16
[ Problem Solving :: 백준 ] 4386 / 별자리 만들기  (0) 2021.11.15
[ Problem Solving :: 백준 ] 5671 / 호텔 방 번호  (0) 2021.11.15

# Link

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

 

2602번: 돌다리 건너기

첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 <악마의 돌다리>와 <천사의 돌다리>를 나타내는

www.acmicpc.net

 

 

# Code - C++

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cassert>
#include <cstring>

using namespace std;

#define endl '\n'
#define len(x) (int)(x).length()
#define size(x) (int)(x).size()
#define str(x) to_string(x)
#define error logic_error("line " + str(__LINE__))

// Set up : Definitions
/* None */

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    string S; cin >> S;
    string D; cin >> D;
    string A; cin >> A;

    // Process
    assert(len(D) == len(A));

    string G[] = {D, A};
    int dp[2][len(D)][len(S)];
    memset(dp, 0, sizeof(dp));

    for (int i=0; i<2; i++) {
        for (int j=0; j<len(D); j++) {
            if (G[i][j] == S[0]) {
                dp[i][j][0] = 1;
            }
        }
    }

    for (int idx=1; idx<len(S); idx++) {
        for (int i=0; i<2; i++) {
            for (int j=0; j<len(D); j++) {
                if (G[i][j] == S[idx]) {
                    for (int k=0; k<j; k++) {
                        if (G[1-i][k] == S[idx-1]) {
                            dp[i][j][idx] += dp[1-i][k][idx-1];
                        }
                    }
                }
            }
        }
    }

    int ans = 0;
    for (int i=0; i<2; i++) {
        for (int j=0; j<len(D); j++) {
            ans += dp[i][j][len(S)-1];
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */

 

 

지적, 조언, 첨언 모두 환영합니다!!!
저작자표시 비영리 변경금지 (새창열림)

'Problem Solving > 백준' 카테고리의 다른 글

[ Problem Solving :: 백준 ] 14606 / 피자 (Small)  (0) 2021.11.16
[ Problem Solving :: 백준 ] 2616 / 소형기관차  (0) 2021.11.16
[ Problem Solving :: 백준 ] 4386 / 별자리 만들기  (0) 2021.11.15
[ Problem Solving :: 백준 ] 5671 / 호텔 방 번호  (0) 2021.11.15
[ Problem Solving :: 백준 ] 10699 / 오늘 날짜  (0) 2021.11.15

# Link

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

 

4386번: 별자리 만들기

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일

www.acmicpc.net

 

 

# Code - C++

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <cmath>

using namespace std;

#define endl '\n'
#define len(x) (int)(x).length()
#define size(x) (int)(x).size()
#define str(x) to_string(x)
#define error logic_error("line " + str(__LINE__))

// Set up : Definitions
const int MAX = 100;
struct Point { double x, y; };
struct Edge { int fr, to; double dist; };

// Set up : Global Variables
int P[MAX], R[MAX];

// Set up : Functions Declaration
bool operator < (const Edge &u, const Edge &v);
int find(int x);
void merge(int x, int y);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int n; cin >> n;
    Point S[n];
    for (int i=0; i<n; i++)
        cin >> S[i].x >> S[i].y;

    // Process
    for (int i=0; i<n; i++) {
        P[i] = i;
        R[i] = 1;
    }

    vector<Edge> E(n*(n-1)/2);
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            double dx = S[i].x - S[j].x;
            double dy = S[i].y - S[j].y;
            double dist = sqrt(dx*dx + dy*dy);
            E.push_back({i, j, dist});
        }
    }

    sort(E.begin(), E.end());

    int cnt = 0;
    double ans = 0;
    for (auto [fr, to, dist] : E) {
        if (find(fr) == find(to)) continue;
        merge(fr, to);
        cnt++, ans += dist;
        if (cnt == n-1) break;
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
bool operator < (const Edge &u, const Edge &v)
{
    auto ut = make_tuple(u.dist, u.fr, u.to);
    auto vt = make_tuple(v.dist, v.fr, v.to);
    return ut < vt;
}

int find(int x)
{
    if (P[x] == x) return x;
    return P[x] = find(P[x]);
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y) return;

    if (R[x] < R[y]) { swap(x, y); }

    P[y] = x;

    if (R[x] == R[y]) { R[x]++; }
}

 

 

지적, 조언, 첨언 모두 환영합니다!!!
저작자표시 비영리 변경금지 (새창열림)

'Problem Solving > 백준' 카테고리의 다른 글

[ Problem Solving :: 백준 ] 2616 / 소형기관차  (0) 2021.11.16
[ Problem Solving :: 백준 ] 2602 / 돌다리 건너기  (0) 2021.11.16
[ Problem Solving :: 백준 ] 5671 / 호텔 방 번호  (0) 2021.11.15
[ Problem Solving :: 백준 ] 10699 / 오늘 날짜  (0) 2021.11.15
[ Problem Solving :: 백준 ] 11657 / 타임머신  (0) 2021.11.15

+ Recent posts

티스토리툴바