22.05.10. 풀었던 문제들

1. 숫자 게임 (greedy)

greedy 문제. A와 B 둘 다 오름차순으로 정렬해 두고 index를 비교한다. 만약 B가 이기는 경우면 상관없지만 A가 이기는 경우에는 B[i]를 버리고 B[i+k]를 택해 더 작은 숫자를 버리고, 이길 수 있는 숫자를 택한다.

// 숫자 게임
using namespace std;
int solution(vector<int> A, vector<int> B) {
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    int ai, bi;
    for(ai = 0, bi = 0; ai < A.size() && bi < B.size();){
        if(A[ai] >= B[bi]){
            bi++;
        } else{
            ai++; bi++;
        }
    }
    
    return ai;
}

 

2. 멀리뛰기

간단한 DP 문제다. 피보나치 수로 풀린다.

마지막에 1칸을 뛰는 경우 -> dp[i-1]의 경우의 수들에서 1을 더하면 되고

마지막에 2칸을 뛰는 경우 -> dp[i-2]의 경우의 수들에서 2를 더하면 i가 나오기 때문.

​

​

3. 거스름돈

dp 문제다. 화폐를 n-1종류 사용했을 때, n번째 화폐의 금액(m이라고 하자)을 추가해서 T원을 만드는 경우 -> dp[T] = dp[T] + dp[T - m]이다. dp[T-m]의 경우 T-m의 금액을 만드는 경우의 수인데, 여기에 m원을 더하면 T가 되기 때문. 그리고 n-1개의 화폐를 사용해 dp[T]가 구해졌을 수도 있기 때문에 +=를 해준다.

​

​

4. 스티커 모으기(2)