#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
using namespace std;
 
int N;
int tower[500010];
int result[500010];
stack<pair<int, int>> st;
 
int main(void)
{
//    freopen("B2493_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> tower[i];
    }
    
    for(int i = N; i >= 1; i--)
    {
        if(st.empty())
        {
            st.push({tower[i], i});
            continue;
        }
        else
        {
            while(!st.empty() && st.top().first < tower[i])
            {
                result[st.top().second] = i;
                st.pop();
            }
            
            st.push({tower[i], i});
        }
    }
    
    for(int i = 1; i <= N; i++)
    {
        cout << result[i] << " ";
    }
    
    return 0;
}
cs
저작자표시
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
 
int N;
int test[1000010];
int super, sub;
long long ans;
 
int main(void)
{
//    freopen("B13458_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> test[i];    
    }
    
    cin >> super >> sub;
    
    for(int i = 1; i <= N; i++)
    {
        test[i] -= super;
        ans++;
    }
    
    for(int i = 1; i <= N; i++)
    {
        if(test[i] <= 0)
        {
            continue;
        }
        else
        {
            if(test[i] % sub == 0)
            {
                ans += test[i] / sub;
            }
            else
            {
                ans += test[i] / sub + 1;
            }
        }
    }
    
    cout << ans;
    
    return 0;
}
cs
저작자표시

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

[백준 12100] 2048(Easy) (C/C++) (★)  (0) 2020.04.29
[백준 14891] 톱니바퀴 (Simulation) (C/C++) (★)  (0) 2020.04.09
[백준 16235] 나무 재테크 (Simulation) (C/C++) (★)  (0) 2020.03.27
[백준 15685] 드래곤 커브 (Simulation) (C/C++) (★★)  (0) 2020.03.27
[백준 14890] 경사로 (Simulation) (C/C++) (★★)  (0) 2020.03.27
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
 
int N;
int RotateNum;
int result;
deque<int> gear[5];
 
void Rotate(int visited[5], int num, int dir)
{
    visited[num] = 1;
    
    // 좌측 비교 
    if(num-1 >= 1 && gear[num][6] != gear[num-1][2] && visited[num-1] == 0)
    {
        if(dir == 1)
        {
            Rotate(visited, num-1, -1);    
        }
        else
        {
            Rotate(visited, num-1, 1);
        }
    } 
    
    // 우측 비교 
    if(num+1 <= 4 && gear[num][2] != gear[num+1][6] && visited[num+1] == 0)
    {
        if(dir == 1)
        {
            Rotate(visited, num+1, -1);    
        }
        else
        {
            Rotate(visited, num+1, 1);
        }
    } 
    
    // 시계방향 
    if(dir == 1)
    {
        int temp = gear[num].back();
        gear[num].pop_back();
        gear[num].push_front(temp); 
    }
    // 반시계방향 
    else
    {
        int temp = gear[num].front();
        gear[num].pop_front();
        gear[num].push_back(temp);
    }
}
 
int main(void)
{
//    freopen("B14891_input.txt", "r", stdin);
    
    for(int i = 1; i <= 4; i++)
    {
        string input;
        cin >> input;    
        
        for(int j = 0; j < input.size(); j++)
        {
            gear[i].push_back(input[j]-'0');
        }
    }
    
    cin >> RotateNum;
    
    while(RotateNum--)
    {
        int visited[5] = {0};
        int num, dir;
        cin >> num >> dir;
        
        Rotate(visited, num, dir);
    }
    
    for(int i = 1; i <= 4; i++)
    {
        if(gear[i][0] == 1)
        {
            if(i == 1)
            {
                result += 1;
            }
            else if(i == 2)
            {
                result += 2;
            }
            else if(i == 3)
            {
                result += 4;
            }
            else if(i == 4)
            {
                result += 8;
            }
        }
    }
    
    cout << result;
    
    return 0;
}
cs
저작자표시

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

[백준 12100] 2048(Easy) (C/C++) (★)  (0) 2020.04.29
[백준 13458] 시험감독 (Simulation) (C/C++)  (0) 2020.04.09
[백준 16235] 나무 재테크 (Simulation) (C/C++) (★)  (0) 2020.03.27
[백준 15685] 드래곤 커브 (Simulation) (C/C++) (★★)  (0) 2020.03.27
[백준 14890] 경사로 (Simulation) (C/C++) (★★)  (0) 2020.03.27
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
 
int N;
int relation[25][25];
vector<int> start_candidate;
int Min = 99999999;
 
void combination(int idx, int cnt)
{
    if(cnt == N/2)
    {
        int start = 0;
        int link = 0;
        vector<int> link_candidate;
        int visited[25] = {0};
        
        for(int i = 0; i < start_candidate.size(); i++)
        {
            for(int j = 0; j < start_candidate.size(); j++)
            {
                if(i == j)
                {
                    continue;
                }
                
                start += relation[start_candidate[i]][start_candidate[j]];
            }
        }
        
        for(int i = 0; i < start_candidate.size(); i++)
        {
            visited[start_candidate[i]] = 1;    
        }
        
        for(int i = 1; i <= N; i++)
        {
            if(visited[i] == 0)
            {
                link_candidate.push_back(i);
            }
        }
        
        for(int i = 0; i < link_candidate.size(); i++)
        {
            for(int j = 0; j < link_candidate.size(); j++)
            {
                if(i == j)
                {
                    continue;
                }
                
                link += relation[link_candidate[i]][link_candidate[j]];
            }
        }
        
        if(Min > abs(start-link))
        {
            Min = abs(start-link);
        }
        
        return;
    }
    
    for(int i = idx; i <= N; i++)
    {
        start_candidate.push_back(i);
        combination(i+1, cnt+1);
        start_candidate.pop_back();
    }
}
 
int main(void)
{
//    freopen("B14889_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            cin >> relation[i][j];
        }
    }
    
    combination(1, 0);
    
    cout << Min;
    
    return 0;
}
cs
저작자표시

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

[백준 1062] 가르침 (조합) (C/C++)  (0) 2020.03.24
[백준 1018] 체스판 다시 칠하기 (Brute Force) (C/C++)  (0) 2020.03.24
[백준 1251] 단어 나누기 (조합) (C/C++) (★)  (0) 2020.03.23
[백준 1041] 주사위 (조합) (C/C++)  (0) 2019.12.18
[백준 15683] 감시 (순열) (C/C++) (★★★)  (1) 2019.11.21
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[110][110];
int visited[110][110];
int row, col;
int time;
 
queue<pair<int, int>> q;
 
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 < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void paint(int x, int y, int level)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        int x = c.front().first;
        int y = c.front().second;
        c.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] != 1 && visited[xpos][ypos] == 0)
            {
                map[xpos][ypos] = level;
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
void init(int x, int y)
{
    int cnt = 0;
    
    for(int k = 0; k < 4; k++)
    {
        int xpos = x+dx[k];
        int ypos = y+dy[k];
        
        if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 2)
        {
            cnt++;
        }
    }
    
    if(cnt >= 2)
    {
        q.push({x, y});
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        map[x][y] = 2;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int main(void)
{
//    freopen("B2638_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
        }
    }
    
    // 치즈는 1, 바깥쪽은 2, 안쪽은 3~ 색칠 
    int level = 2;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                paint(i, j, level);
                level++;    
            }
        }
    }
    
    while(1)
    {    
        memset(visited, 0, sizeof(visited));
        
        time++;
        
        // 바깥쪽과 2면 이상 접촉하는 치즈, 큐에 삽입 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 1)
                {
                    init(i, j);            
                }
            }
        }
        
        melt();
        
        // 치즈가 녹아서 바깥쪽과 안쪽이 연결되었으면 다시 2로 색칠 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 2 && visited[i][j] == 0)
                {
                    paint(i, j, 2);
                }
            }
        }
        
        if(check() == 1)
        {
            cout << time;
            break;
        }
    }
    
    return 0;
}
cs
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[110][110];
int visited[110][110];
int row, col;
int time;
 
queue<pair<int, int>> q;
 
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 < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void paint(int x, int y, int level)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        int x = c.front().first;
        int y = c.front().second;
        c.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] != 1 && visited[xpos][ypos] == 0)
            {
                map[xpos][ypos] = level;
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
void init(int x, int y)
{
    int cnt = 0;
    
    for(int k = 0; k < 4; k++)
    {
        int xpos = x+dx[k];
        int ypos = y+dy[k];
        
        if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 2)
        {
            cnt++;
        }
    }
    
    if(cnt >= 2)
    {
        q.push({x, y});
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        map[x][y] = 2;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int main(void)
{
//    freopen("B2638_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
        }
    }
    
    // 치즈는 1, 바깥쪽은 2, 안쪽은 3~ 색칠 
    int level = 2;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                paint(i, j, level);
                level++;    
            }
        }
    }
    
    while(1)
    {    
        memset(visited, 0, sizeof(visited));
        
        time++;
        
        // 바깥쪽과 2면 이상 접촉하는 치즈, 큐에 삽입 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 1)
                {
                    init(i, j);            
                }
            }
        }
        
        melt();
        
        // 치즈가 녹아서 바깥쪽과 안쪽이 연결되었으면 다시 2로 색칠 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 2 && visited[i][j] == 0)
                {
                    paint(i, j, 2);
                }
            }
        }
        
        if(check() == 1)
        {
            cout << time;
            break;
        }
    }
    
    return 0;
}
cs
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[110][110];
int visited[110][110];
int row, col;
int time;
 
queue<pair<int, int>> q;
 
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 < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void paint(int x, int y, int level)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        int x = c.front().first;
        int y = c.front().second;
        c.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] != 1 && visited[xpos][ypos] == 0)
            {
                map[xpos][ypos] = level;
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
void init(int x, int y)
{
    int cnt = 0;
    
    for(int k = 0; k < 4; k++)
    {
        int xpos = x+dx[k];
        int ypos = y+dy[k];
        
        if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 2)
        {
            cnt++;
        }
    }
    
    if(cnt >= 2)
    {
        q.push({x, y});
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        map[x][y] = 2;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int main(void)
{
//    freopen("B2638_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
        }
    }
    
    // 치즈는 1, 바깥쪽은 2, 안쪽은 3~ 색칠 
    int level = 2;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                paint(i, j, level);
                level++;    
            }
        }
    }
    
    while(1)
    {    
        memset(visited, 0, sizeof(visited));
        
        time++;
        
        // 바깥쪽과 2면 이상 접촉하는 치즈, 큐에 삽입 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 1)
                {
                    init(i, j);            
                }
            }
        }
        
        melt();
        
        // 치즈가 녹아서 바깥쪽과 안쪽이 연결되었으면 다시 2로 색칠 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 2 && visited[i][j] == 0)
                {
                    paint(i, j, 2);
                }
            }
        }
        
        if(check() == 1)
        {
            cout << time;
            break;
        }
    }
    
    return 0;
}
cs
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[110][110];
int visited[110][110];
int row, col;
int time;
 
queue<pair<int, int>> q;
 
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 < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void paint(int x, int y, int level)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        int x = c.front().first;
        int y = c.front().second;
        c.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] != 1 && visited[xpos][ypos] == 0)
            {
                map[xpos][ypos] = level;
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
void init(int x, int y)
{
    int cnt = 0;
    
    for(int k = 0; k < 4; k++)
    {
        int xpos = x+dx[k];
        int ypos = y+dy[k];
        
        if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 2)
        {
            cnt++;
        }
    }
    
    if(cnt >= 2)
    {
        q.push({x, y});
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        map[x][y] = 2;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int main(void)
{
//    freopen("B2638_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
        }
    }
    
    // 치즈는 1, 바깥쪽은 2, 안쪽은 3~ 색칠 
    int level = 2;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                paint(i, j, level);
                level++;    
            }
        }
    }
    
    while(1)
    {    
        memset(visited, 0, sizeof(visited));
        
        time++;
        
        // 바깥쪽과 2면 이상 접촉하는 치즈, 큐에 삽입 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 1)
                {
                    init(i, j);            
                }
            }
        }
        
        melt();
        
        // 치즈가 녹아서 바깥쪽과 안쪽이 연결되었으면 다시 2로 색칠 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 2 && visited[i][j] == 0)
                {
                    paint(i, j, 2);
                }
            }
        }
        
        if(check() == 1)
        {
            cout << time;
            break;
        }
    }
    
    return 0;
}
cs
저작자표시

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

[백준 1939] 중량제한 (BFS, BinarySearch) (C/C++) (★★★)  (0) 2020.05.24
[백준 4991] 로봇 청소기 (BFS, Bitmask) (C/C++) (★★★)  (0) 2020.05.21
[백준 2589] 보물섬 (BFS) (C/C++)  (0) 2020.04.07
[백준 1938] 통나무 옮기기 (BFS) (C/C++) (★★★)  (0) 2020.02.19
[백준 1261] 알고스팟 (BFS) (C/C++) (★★)  (0) 2020.02.16
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
char map[50][50];
int visited[50][50];
int row, col;
int Max;
 
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 < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS(int x, int y)
{
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = 1;
    
    while(!q.empty())
    {
        x = q.front().first;
        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] == 'L' && visited[xpos][ypos] == 0)
            {
                visited[xpos][ypos] = visited[x][y] + 1;
                q.push({xpos, ypos});
                
                if(Max < visited[xpos][ypos])
                {
                    Max = visited[xpos][ypos];
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2589_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        string input;
        cin >> input;
        
        for(int j = 0; j < col; j++)
        {
            map[i][j] = input[j];
        }
    }
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 'L')
            {
                memset(visited, 0, sizeof(visited));
                BFS(i, j);
            }
        }
    }
    
    cout << Max-1;
    
    return 0;
}
 
cs
저작자표시

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

[백준 4991] 로봇 청소기 (BFS, Bitmask) (C/C++) (★★★)  (0) 2020.05.21
[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
[백준 1938] 통나무 옮기기 (BFS) (C/C++) (★★★)  (0) 2020.02.19
[백준 1261] 알고스팟 (BFS) (C/C++) (★★)  (0) 2020.02.16
[백준 1167] 트리의 지름 (BFS, Tree) (C/C++) (★)  (0) 2020.02.16
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
 
long long N, C;
long long house[200010];
 
long long cal(long long mid)
{
    long long cnt = 1;
    int beforeWifi = 1;
    
    for(int i = 2; i <= N; i++)
    {
        if(house[i] - house[beforeWifi] >= mid)
        {
            cnt++;
            beforeWifi = i;
        }
    }
    
    return cnt; 
}
 
int main(void)
{
//    freopen("B2110_input.txt", "r", stdin);
 
    cin >> N >> C;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> house[i];
    } 
    sort(house+1, house+N+1);
    
    long long left = 1;
    long long right = house[N]-house[1];
    long long Max = 0;
    
    while(left <= right)
    {
        // 공유기 사이의 거리 
        long long mid = (left + right) / 2;
        
        // 설치한 공유기 수 
        long long wifi = cal(mid);
        
        if(wifi >= C)
        {
            if(Max < mid)
            {
                Max = mid;
            }
            
            left = mid+1;
        }
        else if(wifi < C)
        {
            right = mid-1;
        }
    }
    
    cout << Max;
 
    return 0;
}
cs
저작자표시

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

[백준 2512] 예산 (Binary Search) (C/C++) (★)  (0) 2020.03.31
[백준 2869] 달팽이는 올라가고 싶다 (Binary Search) (C/C++)  (0) 2020.03.31
[백준 2805] 나무 자르기 (Binary Search) (C/C++) (★)  (0) 2020.01.28
[백준 1654] 랜선 자르기 (Binary Search) (C/C++) (★)  (0) 2020.01.28
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
 
long long N;
long long total;
long long budget[10010];
 
long long cal(long long mid)
{
    long long sum = 0;
    
    for(int i = 1; i <= N; i++)
    {
        if(budget[i] <= mid)
        {
            sum += budget[i];
        }
        else
        {
            sum += mid;
        }
    }
        
    return sum;
}
 
int main(void)
{
//    freopen("B2512_input.txt", "r", stdin);
 
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> budget[i];
    }
    sort(budget+1, budget+N+1);
    
    cin >> total;
    
    long long left = 1;
    long long right = budget[N];
    long long Max = 0; 
    
    while(left <= right)
    {
        // 상한액 
        long long mid = (left + right) / 2;
        
        // 예산
        long long sum = cal(mid); 
 
        if(sum > total)
        {
            right = mid-1;
        }
        else if(sum <= total)
        {
            if(Max < mid)
            {
                Max = mid;
            }
            
            left = mid+1;
        }
    }
    
    cout << Max;
 
    return 0;
}
 cs
저작자표시

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

[백준 2110] 공유기 설치 (Binary Search) (C/C++) (★★★)  (0) 2020.03.31
[백준 2869] 달팽이는 올라가고 싶다 (Binary Search) (C/C++)  (0) 2020.03.31
[백준 2805] 나무 자르기 (Binary Search) (C/C++) (★)  (0) 2020.01.28
[백준 1654] 랜선 자르기 (Binary Search) (C/C++) (★)  (0) 2020.01.28

+ Recent posts

티스토리툴바