[스터디] 문제 풀이 - 4주차

브 - 17202
실 - 14501, 11568, 11722
골 - 9251, 12865
프 - N으로 표현

---

17202번

문제

제일 앞 원소를 하나씩 꺼내서 바로 다음 원소와 더해주는 작업 반복

파이썬 풀이

from collections import deque #제일 앞 원소를 지속적으로 삭제할 것이므로

A =  list(map(int, input()))
B =  list(map(int, input()))

temp = deque()
for i in range(8):
    temp.append(A[i])
    temp.append(B[i])

while len(temp) > 2:
    for _ in range(len(temp) - 1):
        front = temp.popleft()
        temp.append((temp[0] + front) % 10)
    temp.popleft()
    
print(str(temp[0]) + str(temp[1]))

제일 앞에 있는 원소를 지속적으로 꺼내야하므로 list 보다 시간이 유리한 deque 사용!

C++ 풀이

---

14501번

문제

마지막날부터 앞으로 채워나가며 어떤 일을 할 지 결정

파이썬 풀이

n = int(input())

work = [tuple(map(int, input().split())) for _ in range(n)]
dp = [0 for _ in range(n + 1)]
answer = 0

for i in range(n - 1, -1, -1):
    if work[i][0] + i <= n:
        dp[i] = max(work[i][1] + dp[work[i][0] + i], answer)
        answer = dp[i]
    else:
        dp[i] = answer
        
print(answer)

제일 마지막날부터 판단한다는걸 매번 까먹는다

C++ 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n, answer = 0;
    vector<int> T;
    vector<int> P;

    scanf("%d", &n);

    for(int i = 0; i < n; ++i){
        int t, p;
        scanf("%d %d", &t, &p);
        T.push_back(t);
        P.push_back(p);
    }

    vector<int> dp(n+1);
    for(int j = n - 1; j > -1; --j){
        int end_day = T[j] + j;
        if(end_day <= n){
            dp[j] = max(P[j] + dp[end_day], answer);
            answer = dp[j];
        }
        else{dp[j] = answer;}
    }

    printf("%d", answer);
}

11568번

문제

자신보다 작은 수가 몇 개나 나왔는지, 몇 개나 연속으로 이어졌는지 누적해서 체크

파이썬 풀이

n = int(input())
card = list(map(int, input().split()))

dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if card[i] > card[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

C++ 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin >> n;

    vector<int> dp(n, 1);
    vector<int> card(n);

    for(int i = 0; i < n; ++i){
        cin >> card[i];
    }
    for(int i = 1; i < n; ++i){
        for(int j = 0; j < i; ++j){
            if(card[i] > card[j]){
                dp[i] = max(dp[i], dp[j] + 1);
            }              
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
}

처음에 문제 이해를 잘못해서 연속하는 수들만 체크했다..
한 번 틀리고 다시 보니 꼭 붙어있는 수가 아니어도 되는 문제였다. (LIS 문제)
문제를 잘.. 읽자!!!!

11722번

문제

LDS 문제, LIS 문제에서 부등호 방향만 반대

파이썬 풀이

n = int(input())
seq = list(map(int, input().split()))

dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if seq[i] < seq[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

C++ 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin >> n;

    vector<int> dp(n, 1);
    vector<int> seq(n);

    for(int i = 0; i < n; ++i){
        cin >> seq[i];
    }
    for(int i = 1; i < n; ++i){
        for(int j = 0; j < i; ++j){
            if(seq[i] < seq[j]){
                dp[i] = max(dp[i], dp[j] + 1);
            }              
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
}

---

9251번

문제

양쪽 알파벳을 하나씩 비교해서 dp 체크

파이썬 오답

string_a = input()
string_b = input()

a = len(string_a)
b = len(string_b)

dp = [0] * b

check = 0

for i in range(a):
    for j in range(check, b):
        if string_a[i] == string_b[j]:
            for k in range(j, b):
                dp[k] += 1
            check = j
            break

print(max(dp))

문제 예제 입력이 하나뿐이라 되는 건줄 알았다,,
반례 생각하는거 너무 어려워

파이썬 풀이

string_a = input()
string_b = input()

a = len(string_a)
b = len(string_b)

dp = [[0] * (b+1) for _ in range(a+1)]

for i in range(1, a + 1):
    for j in range(1, b + 1):
        if string_a[i - 1] == string_b[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print(max(dp[a]))

2차원으로 dp로 풀어야 하는 문제!
가로 세로 모두 0번은 마진으로 잡아줘야 한 칸 앞에서부터 결과를 당겨올 수 있다.

C++ 풀이

12865번

문제

냅색 알고리즘 - 쪼갤 수 없는 경우

파이썬 오답

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

weight = []
value = []

for _ in range(n):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

dp = value
    
for i in range(1, n):
    temp = weight[i]
    for j in range(i):
        if temp + weight[j] <= k and dp[i] < dp[i] + value[j]:
            temp += weight[j]
            dp[i] += value[j]
            
print(max(dp))

이 문제도.. 2차원으로 푸셔야합니도,,

파이썬 풀이

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

item = [tuple(map(int, input().split())) for _ in range(n)]

dp = [[0] * (k + 1) for _ in range(n + 1)]
    
for i in range(1, n + 1):
    w = item[i - 1][0]
    v = item[i - 1][1]
    for j in range(1, k + 1):
        if j < w:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j])         
            
print(dp[n][k])

고려해야 할 사항이 2개라면 dp도 2차원으로 구성한다.

C++ 풀이

---

N으로 표현

문제

파이썬 풀이

C++ 풀이