LeetCode Weekly Contest 231

A.Check if Binary String Has at Most One Segment of Ones

‘1’이 연속으로 붙어있는 부분이 있는지 확인하는 문제이다.

class Solution {
public:
    bool checkOnesSegment(string s) {
        int last=-1;
        for(int i=s.size()-1;i>0;i--) {
            if(s[i]=='1') {
                last=i;
                break;
            }
        }
        for(int i=1;i<=last;i++) {
            if(s[i]=='0') return false;
        }
        return true;
    }
};

---

B. Minimum Elements to Add to Form a Given Sum

nums배열의 합계를 goal에 맞추기 위해 더해야하는 limit보다 작거나 같은 정수들의 최소 수를 구하는 문제이다.

단순하게 nums의 합계와 goal의 차이를 구한 후에 limit으로 나눠 나머지가 남게되면 1을 추가하는 방법으로 구할 수 있다.

class Solution {
public:
    int minElements(vector<int>& nums, int limit, int goal) {
        long long sum=0;
        for(auto it : nums) sum+=it;
        long long diff=abs(goal-sum);
        limit=abs(limit);
        return diff/(long long)(limit)+(diff%limit!=0);
    }
};

---

C. Number of Restricted Paths From First to Last Node

주어진 그래프에서 최단거리를 의미하는 distanceToLastNode(x)를 구하고 distanceToLastNode(zi) > distanceToLastNode(zi+1), 0 <= i <= k-1를 만족하는 경로의 수를 구하는 문제이다.

다익스트라로 최단거리를 구해준 후 dfs로 위의 식을 만족하는 경로의 수를 구해주면 된다.

class Solution {
public:
    vector<pair<int,int>> graph[20001];
    const long long mod=1e9+7;
    long long dist[20001];
    long long dp[20001];
    
    void dijkstra(int n) {
        priority_queue<pair<long long,int>> pq;
        pq.push({0,n});
        dist[n]=0;
        while(!pq.empty()) {
            long long distance=-pq.top().first;
            int node=pq.top().second;
            pq.pop();
            if(dist[node]<distance) continue;
            for(int i=0;i<graph[node].size();i++) {
                int next=graph[node][i].first;
                long long next_distance=graph[node][i].second+distance;
                if(dist[next]>next_distance) {
                    dist[next]=next_distance;
                    pq.push({-next_distance,next});
                }
            }
        }
    }
    
    long long dfs(int n) {
        if(n==1) {
            return 1;
        }
        
        long long &ret=dp[n];
        if(ret!=-1) return ret%mod;
        ret=0;
        
        for(int i=0;i<graph[n].size();i++) {
            int next=graph[n][i].first;
            if(dist[next]>dist[n]) {
                ret+=dfs(next);
                ret%=mod;
            }
        }
        
        return ret%mod;
    }
    
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        for(int i=0;i<edges.size();i++) {
            int u=edges[i][0], v=edges[i][1], w=edges[i][2];
            graph[u].push_back({v,w});
            graph[v].push_back({u,w});
        }
        
        memset(dist,mod,sizeof(dist));
        dijkstra(n);
        
        memset(dp,-1,sizeof(dp));
        
        return (int)(dfs(n)%mod);
    }
};

---

D. Make the XOR of All Segments Equal to Zero