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

num = int(input())
d = [0] * (num+1)

for i in range(1, num + 1):
    d[i] = i  
    j = 1
    while j * j <= i:
        d[i] = min(d[i], d[i - j * j] + 1)
        j += 1

print(d[num])

1004

import collections

caseNum = int(input())
arr = input().split()
counter = collections.Counter(arr)

num = int(input())
searchNums = input().split()

for s in searchNums:
    print(counter[s], end=' ')

1005

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

int main() {
	int num(0);
	cin >> num;
	int x, y;
    vector <pair<int, int>> arr;
	
	for (int i = 0; i < num; i++){
		cin >> x >> y;
		arr.push_back({x,y});
	}
	sort(arr.begin(),arr.end());
	
	for (auto &v : arr) {
        cout << v.first << " " << v.second << "\n";
    }
    return 0;
}

 

1006

num, maxWeight = map(int, input().split())

d = [0] * (maxWeight+1)
for i in range(num):
    weight, value = map(int, input().split())
    for w in range(maxWeight, weight - 1, -1): 
        d[w] = max(d[w], d[w - weight]+ value)
print(d[maxWeight])

 

1007

이날 레제 극장판을 너무 감명깊게 봐서 폭발하는 문제를 찾아서 풀었음

text = input()
bomb = input()

stack = []
bomb_len = len(bomb)

for ch in text:
    stack.append(ch)

    if len(stack) >= bomb_len and ''.join(stack[-bomb_len:]) == bomb:
        del stack[-bomb_len:]

    
result = ''.join(stack)
print(result if result else "FRULA")

 

1008

casenum = int(input())

for i in range(casenum):
    num = int(input())
    d = [0] * (num + 1)

    d[1] = 1
    if num >= 2:
        d[2] = 2
    if num >= 3:
        d[3] = 4

    for j in range(4, num +1):
        d[j] = d[j-1] + d[j-2] + d[j-3]
    print(d[num])

 

1009

 

def func(num):
    if(num <= 1):
        return 1
    return num * func(num-1)

num = int(input())
facNum = func(num)
count = 0

while facNum % 10 == 0:
    count += 1
    facNum //= 10

print(count)

 

1010

num = int(input())
d = [0] * (num+1)

for i in range(1, num + 1):
    d[i] = i  
    j = 1
    while j * j <= i:
        d[i] = min(d[i], d[i - j * j] + 1)
        j += 1

print(d[num])