23.07.27. 풀었던 문제들 복기

2141. Maximum Running Time of N Computers

 binary search로 푸는 문제. 일단 제일 문제가 됐던 것은 time만에 batteries를 사용해서 n개의 computer를 동시에 돌릴 수 있는지를 O(b) 시간 안에 푸는 것이었다.

 여기서 핵심은

• time보다 큰 용량을 가진 battery들은 계속 컴퓨터에 꽂아두면 time만큼 쓸 수 있다.
• 그러면, 나머지, time보다 작은 용량을 가진 battery들로 나머지 컴퓨터의 사용 시간을 채워야 한다.
• 이 둘을 합친 것이 sum += min(time, b)이다.
• 만약 sum이 n*time보다 크다는 것은 battery들로 time만큼 쓸 수 있다는 것을 의미한다.

// Runtime 160 ms Beats 95.32%
// Memory 55.8 MB Beats 71.58%

typedef long long ll;

class Solution {
public:
    // time 안에 batteries 사용해서 n개의 computer 동시 구동 가능?
    // 검사는 O(n)으로 해야함
    bool possible(int n, vector<int>& batteries, ll time){
        ll sum = 0;
        for(int b : batteries){
            if(b > time) sum += time;
            else sum += b;
        }
        // 각 battery들의 합을 더하는데, 최대 time만큼 더함
        // n * time = battery 합이 
        if(sum >= n*time) return true;
        else return false;
    }
    long long maxRunTime(int n, vector<int>& batteries) {
        ll start = 1, end = 1e14+1, mid;
        while(start < end){
            ll mid = (start + end) / 2;
            if(!possible(n, batteries, mid)) end = mid; // not possible then 시간 줄여야 함
            else start = mid + 1;
        }
        return end-1;
    }
};

 

 한편, 제일 마지막에는 end -1을 한다. 왜 할까? 이렇게 구하면 not possible한 값 중 제일 작은 값... 그러니까 possible한 값의 upper bound를 구한다. 그래서 1을 당겨준다.

 

시간복잡도

 parametric search(binary search)이다. possible 함수는 O(b), binary search의 범위는 1e14이므로 O(blog($10^{14}$))이다.

 

공간복잡도

 추가 공간은 안 쓰니까 O(1)

 

실수했던 점

 binary search에서 possible의 위치를 잘못 넣었다. possible이면 시간을 더 늘일 수 있다는 것이므로 start = mid+1의 조건으로 달았어야 했는데, 거꾸로 했다.

 항상 end = mid 조건을 위에 넣다보니 생긴 실수 같다. end = mid라는 것은, 조건이 부합하지 않아 범위를 줄인다는 것을 의미한다. 유념하자.

 

후기

 solution을 보고 풀었다. 다음에 다시 풀어보자.

 

 

 

백준 10421 수식 완성하기

 문제를 구현하기만 하면 되는 문제이다. 모든 경우의 수를 세야 하므로, backtracking을 써서 모든 경우의 수를 계산하는 문제이다. 

set<char> availNums; // 사용 가능한 숫자 목록
vector<int> avails, stars;
int K, N;
int answer = 0;

// n이 사용 가능한지 검사하는 함수, 내부적으로 2가지를 본다.
// 1) 자리 수가 맞는지, 2) 사용 가능한 숫자만 있는지
bool isIntegerAvailable(int n, int len){
    // 1)
    string nstr = to_string(n);
    if(nstr.length() != len) return false;

    // 2)
    for(char c : nstr){
        bool isExist = false;
        for(int avail : avails){
            if(avail + '0' == c) isExist = true;
        }
        if(!isExist) return false;
    }
    return true;
}

// 순열 생성 결과가 문제 조건에 부합하는지 본다.
bool isPossible(int a, int b){
    // 검증
    if(!isIntegerAvailable(a*b, stars[stars.size()-1])) return false;

    int staridx = 2;
    while(b){
        if(!isIntegerAvailable(a * (b%10), stars[staridx])) return false;
        b /= 10;
        staridx++;
    }

    return true;
}

// 중복순열 생성 : A는 위, B는 아래 것.
void dupPermutationB(int depth, int a, int b){
    if(depth == stars[1]){
        if(isPossible(a, b)){
            answer++;
        }
        return;
    }

    for(int i = 0; i<avails.size(); i++){
        dupPermutationB(depth+1, a, 10*b + avails[i]);  
    }
}

void dupPermutationA(int depth, int a){
    if(depth == stars[0]){
        dupPermutationB(0, a, 0);
        return;
    }

    for(int i = 0; i<avails.size(); i++){
        dupPermutationA(depth+1, 10*a + avails[i]);
    }
}

//////////////////////

int main(void) {
    cin.tie(0);
    cout.tie(0);
    std::ios_base::sync_with_stdio(0);

    // input
    cin >> N;
    stars.resize(N);
    for (int i = 0; i < N; i++)
        cin >> stars[i];

    cin >> K;
    avails.resize(K);
    for (int i = 0; i < K; i++)
    {
        cin >> avails[i];
    }

    // solve
    /*
    s1 = 5, s2 = 3인 경우, 총 8개
    9^8 = 4천만, 경우의 수는 충분함.
    100000 * 1000 = 100000000, 곱 연산 결과는 1억보다 작으므로 int를 써도 됨.

    1) s1+s2 PI k로 중복순열 뽑음.
    2) s1과 s2의 각 자리를 연산한다.
        - 자리수가 맞는지
        - 사용 가능한 숫자만 있는지
    3) s1 * s2의 결과값을 본다.
        - 자리수가 맞는지
        - 사용 가능한 숫자만 있는지
    */

    dupPermutationA(0, 0);

    cout << answer;

    return 0;
}

 

시간복잡도

 중복순열, 9$^8$.

 

후기

 문제 구조상 중복순열이기 때문에 9의 8승 이 5천만 정도여서 충분히 풀릴 것으로 생각했으나, 계속 시간 초과가 떴다. (기존 방식은 string을 사용해 풀었다.) 

 다른 사람들의 solution을 보니, 대부분 integer 형태로 푼 것을 알 수 있었다. 나도 똑같이 string을 integer로 바꿨을 뿐인데 바로 해결되었다. 아마 string으로 사용하는 경우, backtracking에서 매번 string 뒤에 뭘 붙이기 때문에 추가할 때도 많이 걸리고, 비교할 때도 많이 걸린다. 예를 들어 integer 2개를 비교할 때는 32bit 2개만 비교하면 되지만, string의 내부 char를 모두 봐야 하기에, 비교/추가할 때는 시간이 많이 걸린다고 한다. stack overflow link

 하,, 로직은 맞았는데 이런 내부 로직 몰라서 틀릴 때 좀 화가 난다. ㅠㅠ 앞으로 시간이 빠듯할 것 같을 때는 string 말고 int를 쓰자.