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

1108

#include <iostream>
using namespace std;

long long p[101]; 

int main() {


    int k;
    cin >> k;

    p[1] = p[2] = p[3] = 1;
    p[4] = p[5] = 2;

    for (int i = 6; i <= 100; i++) {
        p[i] = p[i - 1] + p[i - 5];
    }

    while (k--) {
        int n;
        cin >> n;
        cout << p[n] << '\n';
    }

    return 0;
}

 

1109

num, n = map(int, input().split())
count = 0
arr = set()  

for _ in range(num):
    arr.add(input())

for _ in range(n):
    word = input()
    if word in arr:
        count += 1

print(count)

 

1110

n, k = map(int, input().split())
arr = list(map(int, input().split()))

count = 0
found = False

for i in range(n - 1, 0, -1):  
    max_idx = i
    for j in range(i - 1, -1, -1):
        if arr[j] > arr[max_idx]:
            max_idx = j

    if max_idx != i:
        arr[i], arr[max_idx] = arr[max_idx], arr[i]
        count += 1
        if count == k:
            print(arr[max_idx], arr[i])
            found = True
            break

if not found:
    print(-1)

 

1111

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

int main() {
int casenum, num;

cin >> casenum;

for (int i = 0; i < casenum; i++){
int count(1);
cin >> num;
vector<pair<string, string>> arr(num);
map<string, int> typeCount;

for (int j = 0; j < num; j++){
cin >> arr[j].first >> arr[j].second;
typeCount[arr[j].second]++;
}

for (auto &p : typeCount) {
count *= (p.second + 1);
}

count -= 1;

cout << count << "\n";

}


return 0;
}

 

1112

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

int main() {

    int num(0), caseNum(0), k(0);
    scanf("%d %d", &num, &caseNum);

    vector<int> arr(num + 1, 0); 
    for (int i = 1; i <= num; i++) {
        scanf("%d", &k);
        arr[i] = arr[i - 1] + k; 
    }

    for (int i = 0; i < caseNum; i++) {
        int startNum(0), endNum(0);
        scanf("%d %d", &startNum, &endNum);
        printf("%d\n", arr[endNum] - arr[startNum - 1]);
    }
    return 0;
}

 

1113

def cutSum(arr, height):
total = 0
for ch in arr:
if ch > height:
total += ch - height
return total

def binary_search(arr, minsum):
left = 0
right = max(arr)
result = 0

while left <= right:
mid = (left + right) // 2
cutsum = cutSum(arr, mid)

if cutsum >= minsum:
result = mid
left = mid +1
else:
right = mid -1

return result

num, minsum = map(int, input().split())
arr = list(map(int, input().split()))


print(binary_search(arr, minsum))

 

1114

def func(start):
    heap = []
    dist[start] = 0
    heapq.heappush(heap, (0, start))

    while heap:
        current_cost, now = heapq.heappop(heap)

        if dist[now] < current_cost:
            continue

        for nxt, cost in graph[now]:
            new_cost = current_cost + cost
            if new_cost < dist[nxt]:
                dist[nxt] = new_cost
                prev[nxt] = now
                heapq.heappush(heap, (new_cost, nxt))

import sys
import heapq
input = sys.stdin.readline

n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, cost = map(int, input().split())
    graph[a].append((b, cost))

start, end = map(int, input().split())

nf = float('inf')
dist = [nf] * (n+1)
prev = [0] * (n+1)

func(start)


path = []
cur = end
while cur != 0:
    path.append(cur)
    cur = prev[cur]

path.reverse()


print(dist[end])         
print(len(path))         
print(*path)