#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
long long cal(vector<int> times, long long mid)
{
    long long peopleCnt = 0;
    
    for(int i = 0; i < times.size(); i++)
    {
        if(times[i] > mid)
        {
            break;
        }
        
        peopleCnt += mid / times[i];
    }
    
    return peopleCnt;
}
 
long long solution(int n, vector<int> times) 
{
    long long Min = 200000000000000;
    
    sort(times.begin(), times.end());
    
    long long left = 1;
    long long right = (long long)times[times.size()-1] * n;
    
    while(left <= right)
    {
        long long mid = (left + right) / 2;
        
        long long peopleCnt = cal(times, mid);
        
        if(peopleCnt >= n)
        {
            right = mid-1;
            
            if(mid < Min)
            {
                Min = mid;
            }
        }
        else if(peopleCnt < n)
        {
            left = mid+1;
        }
    }
    
    return Min;
}
cs
저작자표시 (새창열림)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 순위 (C/C++) (★★)  (0) 2020.02.05
[프로그래머스 3] 가장 먼 노드 (C/C++)  (0) 2020.02.05
[프로그래머스 3] 예산 (C/C++)  (0) 2020.01.26
[프로그래머스 3] 등굣길 (C/C++)  (0) 2020.01.14
[프로그래머스 3] 타일 장식물 (C/C++)  (0) 2020.01.11
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
long long cal(vector<int> budgets, int limit)
{
    long long sum = 0;
    
    for(int i = 0; i < budgets.size(); i++)
    {
        if(budgets[i] <= limit)
        {
            sum += budgets[i];
        }
        else
        {
            sum += limit;
        }   
    }
    
    return sum;
}
 
int solution(vector<int> budgets, int M) 
{
    int answer = 0;
    long long Max;
    long long MM = M;
    
    sort(budgets.begin(), budgets.end());
    
    int left = 1;
    int right = budgets[budgets.size()-1];
    
    long long sum = cal(budgets, right);
    if(sum <= MM)
    {
        return right;
    }
    
    while(left <= right)
    {
        int mid = (left+right)/2;
        
        long long sum = cal(budgets, mid);
        
        if(sum > MM)
        {
            right = mid-1;
        }
        else if(sum < MM)
        {
            left = mid+1;
            
            if(sum > Max)
            {
                Max = sum;
                answer = mid;
            }
        }
        else if(sum == MM)
        {
            answer = mid;
            break;
        }
    }
    
    return answer;
}
 cs
저작자표시 (새창열림)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 가장 먼 노드 (C/C++)  (0) 2020.02.05
[프로그래머스 3] 입국 심사 (C/C++)  (0) 2020.01.27
[프로그래머스 3] 등굣길 (C/C++)  (0) 2020.01.14
[프로그래머스 3] 타일 장식물 (C/C++)  (0) 2020.01.11
[프로그래머스 3] 정수 삼각형 (C/C++)  (0) 2020.01.11
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
 
int T;
int N;
int map[100010];
int visited[100010]; // 0: 아직 시도안함 , -1: 팀을 찾음, 나머지: 팀을 못찾음 
bool flag;
vector<int> check; // 팀원 저장용
 
int stopMember;
 
void DFS(int start, int cnt)
{
    if(flag == true)
    {
        return;
    }
        
    if(visited[map[start]] == 0)
    {
        // 팀이 되는 경우에, 사람을 체크하기 위해서 
        check.push_back(map[start]);
        
        visited[map[start]] = cnt;
        DFS(map[start], cnt);
    }
    // 팀이 되는 경우 
    else if(visited[map[start]] == cnt)
    {
        // 처음과 끝이되는 멤버 체크 
        stopMember = map[start];
 
        flag = true;
        
        return;
    }
}
 
int main(void)
{
//    freopen("B9466_input.txt", "r", stdin);
    
    cin >> T;
    
    for(int k = 1; k <= T; k++)
    {
        for(int i = 0; i <= 100000; i++)
        {
            map[i] = 0;
            visited[i] = 0;
        }
        
        cin >> N;
        
        for(int a = 1; a <= N; a++)
        {
            int b;
            cin >> b;
            
            map[a] = b;
        }
        
        int cnt = 1;
        for(int i = 1; i <= N; i++)
        {
            check.clear();
            flag = false;
            
            // 혼자하고 싶어하는 경우 
            if(i == map[i])
            {
                visited[i] = -1;
                continue;
            }
            
            // 팀으로 할 가능성이 있는 경우 
            if(visited[i] == 0)
            {
                visited[i] = cnt;
                check.push_back(i);
                DFS(i, cnt);
                
                if(flag == true)
                {                    
                    // stopMember의 인덱스 찾기
                    int stopMemberIdx; 
                    for(int j = 0; j < check.size(); j++)
                    {
                        if(check[j] == stopMember)
                        {
                            stopMemberIdx = j;    
                            break;                
                        }
                    }    
                    
                    // stopMember부터 팀이 된 사람 -1 체크
                    for(int j = stopMemberIdx; j < check.size(); j++)
                    {
                        visited[check[j]] = -1;
                    }    
                } 
                
                cnt++;
            }
        }
        
        int ans = 0;
        for(int i = 1; i <= N; i++)
        {
            if(visited[i] != -1)
            {
                ans++;
            }
        }
        
        cout << ans << endl;
    }
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > DFS' 카테고리의 다른 글

[백준 1325] 효율적인 해킹 (DFS) (C/C++) (★)  (0) 2020.05.24
[백준 1068] 트리 (DFS, Tree) (C/C++) (★)  (0) 2020.02.16
[백준 2667] 단지번호 붙이기 (DFS) (C/C++)  (0) 2020.01.26
[백준 10451] 순열 사이클 (DFS) (C/C++)  (0) 2020.01.26
[백준 13023] ABCDE (DFS) (C/C++)  (0) 2019.12.08
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int row, col;
int map[1010][1010];
int visited[1010][1010];
int houseNum;
int Size;
vector<int> complex;
 
queue<pair<int, int>> q;
 
int dx[4] = {-1, 1, 0, 0}; // 상하좌우 
int dy[4] = {0, 0, -1, 1}; // 상하좌우
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0 && visited[i][j] == 0)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    int cnt = q.size();
    
    while(cnt--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 0 && visited[xpos][ypos] == 0)
            {
                visited[xpos][ypos] = 1;    
                q.push({xpos, ypos});
            } 
        }
    }
}
 
int main(void)
{
//     freopen("B7576_input.txt", "r", stdin);
    
    cin >> col >> row;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
            
            if(map[i][j] == 1)
            {
                q.push({i, j});
                visited[i][j] = 1;
            }
        }
    }
    
    int time = 0;
    while(1)
    {    
        if(check() == 1)
        {
            cout << time;
            break;
        }
        
        if(q.empty())
        {
            cout << "-1";
            break;
        }
        
        BFS();
        
        time++;    
    }
        
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > BFS' 카테고리의 다른 글

[백준 2146] 다리 만들기 (BFS) (C/C++)  (0) 2020.01.28
[백준 2178] 미로 탐색 (BFS) (C/C++)  (0) 2020.01.28
[백준 1707] 이분 그래프 (BFS) (C/C++) (★)  (0) 2020.01.26
[백준 1525] 퍼즐 (BFS) (C/C++) (★★)  (0) 2019.12.13
[백준 1963] 소수경로 (BFS) (C/C++)  (0) 2019.12.13
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N;
int map[30][30];
int visited[30][30];
int houseNum;
int Size;
vector<int> complex;
 
int dx[4] = {-1, 1, 0, 0}; // 상하좌우 
int dy[4] = {0, 0, -1, 1}; // 상하좌우
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void DFS(int x, int y, int color)
{
    for(int i = 0; i < 4; i++)
    {
        int xpos = x+dx[i];
        int ypos = y+dy[i];
        
        if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 1 && visited[xpos][ypos] == 0)
        {
            visited[xpos][ypos] = color;
            DFS(xpos, ypos, color);
            Size++;
        }
    }
}
 
int main(void)
{
    // freopen("B2667_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            scanf("%1d", &map[i][j]);        
        }
    }
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(map[i][j] == 1 && visited[i][j] == 0)
            {
                Size = 1;
                houseNum++;
                visited[i][j] = houseNum;
                DFS(i, j, houseNum);
                complex.push_back(Size);
            }
        }
    }
    
    cout << houseNum << endl;
    
    sort(complex.begin(), complex.end());
    for(int i = 0; i < complex.size(); i++)
    {
        cout << complex[i] << endl;
    }
        
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > DFS' 카테고리의 다른 글

[백준 1068] 트리 (DFS, Tree) (C/C++) (★)  (0) 2020.02.16
[백준 9466] 텀 프로젝트 (DFS) (C/C++) (★★★)  (0) 2020.01.26
[백준 10451] 순열 사이클 (DFS) (C/C++)  (0) 2020.01.26
[백준 13023] ABCDE (DFS) (C/C++)  (0) 2019.12.08
[백준 14500] 테트로미노 (DFS) (C/C++) (★)  (0) 2019.11.19
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <map>
#include <vector>
using namespace std;
 
int T;
int N;
vector<int> graph[1010];
int visited[1010];
 
void DFS(int start)
{
    visited[start] = 1;
    
    for(int i = 0; i < graph[start].size(); i++)
    {
        if(visited[graph[start][i]] == 0)
        {
            DFS(graph[start][i]);
        }
    }    
}
 
int main(void)
{
//    freopen("B10451_input.txt", "r", stdin);
    
    cin >> T;
    
    for(int k = 1; k <= T; k++)
    {
        for(int i = 1; i <= 1000; i++)
        {
            graph[i].clear();
        }
        memset(visited, 0, sizeof(visited));
        
        cin >> N;
        
        for(int a = 1; a <= N; a++)
        {
            int b;
            cin >> b;
            
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        
        int cnt = 0;
        for(int i = 1; i <= N; i++)
        {
            if(visited[i] == 0)
            {
                DFS(i);
                
                cnt++;
            }
        }
        
        cout << cnt << endl;
    }
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > DFS' 카테고리의 다른 글

[백준 9466] 텀 프로젝트 (DFS) (C/C++) (★★★)  (0) 2020.01.26
[백준 2667] 단지번호 붙이기 (DFS) (C/C++)  (0) 2020.01.26
[백준 13023] ABCDE (DFS) (C/C++)  (0) 2019.12.08
[백준 14500] 테트로미노 (DFS) (C/C++) (★)  (0) 2019.11.19
[백준 10971] 외판원 순회2 (DFS) (C/C++) (★)  (0) 2019.11.19
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
 
int T;
int V, E;
vector<int> graph[20010];
int visited[20010];
 
void BFS(int start)
{    
    queue<int> q;
    
    q.push(start);
    visited[start] = 1; // 빨강(1), 파랑(2), 방문X(0) 
    
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        
        for(int i = 0; i < graph[x].size(); i++)
        {
            // 빨강 
            if(visited[x] == 1)
            {
                // 인접한 곳은 파랑으로 색칠
                if(visited[graph[x][i]] == 0)
                {
                    q.push(graph[x][i]);
                    visited[graph[x][i]] = 2;    
                } 
            }
            // 파랑 
            else if(visited[x] == 2)
            {
                // 인접한 곳은 빨강으로 색칠 
                if(visited[graph[x][i]] == 0)
                {
                    q.push(graph[x][i]);
                    visited[graph[x][i]] = 1;    
                } 
            }
        }
    }
}
 
bool isBinary()
{
    for(int i = 1; i <= V; i++)
    {
        for(int j = 0; j < graph[i].size(); j++)
        {
            // 인접한 정점끼리의 색이 같으면 이분그래프X 
            if(visited[i] == visited[graph[i][j]])
            {
                return false;
            }
        }
    }
    
    return true;
}
 
int main(void)
{
//    freopen("B1981_input.txt", "r", stdin);
    
    cin >> T;
    
    while(T--)
    {
        cin >> V >> E;
        
        for(int i = 1; i <= V; i++)
        {
            graph[i].clear();
            visited[i] = 0;
        }
        
        for(int i = 1; i <= E; i++)
        {
            int from, to;
            cin >> from >> to;
            
            graph[from].push_back(to);
            graph[to].push_back(from);
        }
        
        for(int i = 1; i <= V; i++)
        {
            if(visited[i] == 0)
            {
                BFS(i);    
            }
        }
        
        if(isBinary())
        {
            cout << "YES" << endl;    
        } 
        else
        {
            cout << "NO" << endl;
        }
    }
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > BFS' 카테고리의 다른 글

[백준 2178] 미로 탐색 (BFS) (C/C++)  (0) 2020.01.28
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2020.01.26
[백준 1525] 퍼즐 (BFS) (C/C++) (★★)  (0) 2019.12.13
[백준 1963] 소수경로 (BFS) (C/C++)  (0) 2019.12.13
[백준 16236] 아기상어 (BFS) (C/C++) (★★★★)  (0) 2019.12.13
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
 
long long N, M;
 
long long twoN;
long long twoM;
long long twoNM;
 
long long fiveN; 
long long fiveM;
long long fiveNM;
 
int main(void)
{
//    freopen("B2004_input.txt", "r", stdin);
    
    cin >> N >> M;
    
    for(long long i = 2; i <= N; i *= 2)
    {
        twoN += N / i;
    }
    for(long long i = 2; i <= M; i *= 2)
    {
        twoM += M / i;
    }
    for(long long i = 2; i <= N-M; i *= 2)
    {
        twoNM += (N-M) / i;
    }
    
    for(long long i = 5; i <= N; i *= 5)
    {
        fiveN += N / i;
    }
    for(long long i = 5; i <= M; i *= 5)
    {
        fiveM += M / i;
    }
    for(long long i = 5; i <= N; i *= 5)
    {
        fiveNM += (N-M) / i;
    }
    
    cout << min(twoN-twoM-twoNM, fiveN-fiveM-fiveNM);
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > Math' 카테고리의 다른 글

[백준 4948] 베르트랑 공준 (Eratos) (C/C++)  (0) 2020.03.25
[백준 1676] 팩토리얼 0의 개수 (Math) (C/C++)  (0) 2020.01.25
[백준 11653] 소인수 분해 (Math) (C/C++)  (0) 2020.01.25
[백준 6658] 골드바흐의 추측 (Math) (C/C++) (★)  (0) 2020.01.25
[백준 11576] Base Conversion (Math) (C/C++)  (0) 2020.01.25

+ Recent posts

티스토리툴바