[알고리즘 스터디] 8주차 결산

1122

def d(n):
    return n + sum(map(int, str(n)))

generated = set()

for i in range(1, 10001):
    generated.add(d(i))

for i in range(1, 10001):
    if i not in generated:
        print(i)

 

1123

num = int(input())

line = 1
while num > line * (line + 1) // 2:
    line += 1

line_sum = line * (line + 1) // 2
pos = line_sum - num

if line % 2 == 0:  
    numerator = 1 + pos
    denominator = line - pos
else:  
    numerator = line - pos
    denominator = 1 + pos

print(f"{numerator}/{denominator}")

 

1124

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N, M;
cin >> N >> M;

vector<string> board(N);
for (int i = 0; i < N; i++) {
cin >> board[i];
}

int maxSize = 1; 


for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {


for (int size = 1; i + size < N && j + size < M; size++) {

if (board[i][j] == board[i][j + size] &&
board[i][j] == board[i + size][j] &&
board[i][j] == board[i + size][j + size])
{
maxSize = max(maxSize, size + 1);}
}
}
}

cout << maxSize * maxSize << "\n";
return 0;
}

 

1125

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    vector<int> temp(N);
    for (int i = 0; i < N; i++) {
        cin >> temp[i];
    }

    int currentSum = 0;
    for (int i = 0; i < K; i++) {
        currentSum += temp[i];
    }

    int maxSum = currentSum;

    for (int i = K; i < N; i++) {
        currentSum += temp[i] - temp[i - K];
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }

    cout << maxSum << "\n";

    return 0;
}

 

1126

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    int answer = 0;

    while (N--) {
        string s;
        cin >> s;

        stack<char> st;
        for (char c : s) {
            if (!st.empty() && st.top() == c) {
                st.pop(); 
            } else {
                st.push(c);
            }
        }

        if (st.empty())
            answer++;
    }

    cout << answer << "\n";
    return 0;
}

 

 

 

1128

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> dist(n+1, vector<int>(n+1, INF));
    vector<vector<int>> next(n+1, vector<int>(n+1, 0));

    for (int i = 1; i <= n; i++) dist[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (dist[a][b] > c) {
            dist[a][b] = c;
            next[a][b] = b;   
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];  
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dist[i][j] == INF) cout << 0 << " ";
            else cout << dist[i][j] << " ";
        }
        cout << "\n";
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dist[i][j] == INF || i == j) {
                cout << 0 << "\n";
                continue;
            }

            vector<int> path;
            int cur = i;
            while (cur != j) {
                path.push_back(cur);
                cur = next[cur][j];
            }
            path.push_back(j);

            cout << path.size() << " ";
            for (int x : path) cout << x << " ";
            cout << "\n";
        }
    }

    return 0;
}