알고리즘/백준42 백준 10282 해킹 C++ 간단한 해설 단순하게 다익스트라를 하면 된다. (c에서 시작해서, b->a로 이어지는데, s초가 더해진다.)그러나 단순하게 2차원 배열로 그래프를 만들면 25%정도에서 메모리 초과가 발생한다.나는 그래서 연결리스트로 풀 수 있지만 꼼수로 다음과 같이 그래프 연결이 필요한 부분만 연결하였다.vector>> graph(n+1,vector>());for(int i=0;i>a>>b>>s; graph[b].push_back({a,s});} 답 #include #include #include #include #define ll long longusing namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int t; c.. 2025. 2. 11. 백준 28449 누가 이길까 C++ 간단한 해설 HI팀이 이기는 경우랑 무승부만 세면 자연스럽게 ARC팀이 이기는 경우의 수가 나온다.(전체 경우의 수인 N*M에서 빼면 된다.) 이 때, 전체 경우의 수는 100,000*100,000 이므로 int 자료형의 범위를 넘어가니 long long 형으로 해야한다. HI팀이 이기는 경우의 수는 누적합을 써도 좋지만 나는 간단하게 이분탐색으로 찾았다. upper_bound의 결과값 - lower_bound의 결과값을 하면 간단하게 무승부인 경우의 수를 셀 수 있고,lower_bound의 결과값이 이기는 경우의 수이다. lower_bound는 같거나 큰 값만을 탐색하므로 결과값에서 -1을 해야 하는게 맞지만 Index를 반환하기 때문에(Index가 0부터 시작해서) 따로 처리를 안해주고 결과값 그 .. 2025. 2. 8. 백준 1911 흙길 보수하기 C++ 간단한 해설 진짜 간단하다. 이전에 판자를 어디까지 놓았는지 기억하면 된다. 그런데, 사소한 계산에서 실수를 하기 쉬워서 조금 성가셨다. if(lastPanel>=v[i].second) continue; if(lastPanel>=v[i].first) v[i].first=lastPanel+1; if(v[i].second-v[i].first 스위핑으로 인한 조건 분기를 생각하자... 답 #include #include #include #define ll long longusing namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); ll n,l; cin>>n>>l; vector> v(n); .. 2025. 1. 15. 백준 2636 치즈 C++ 간단한 해설외각부터 벽이 있어서 그냥 단순하게 bfs를 반복하면 된다. c가 된 부분의 값을 큐를 순회하면서 0으로 만드는 방법으로 해결 답#include #include #include #include #define ll long longusing namespace std;int dy[4]={1,-1,0,0};int dx[4]={0,0,1,-1};int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n,m; cin>>n>>m; vector> v(n,vector(m)); for(int i=0;i>v[i][j]; } } int time=0,cheeze=0; while(true){ bool state.. 2025. 1. 9. 백준 2141 우체국 C++ 간단한 해설 N이 최대 10^5, | X[i] |와 A[i] 모두 최대 10^9 이므로 long long형이더라도 overflow가 될 수 있는 가능성을 생각만 해뒀다. 우리가 구하고자 하는 값은 한 지점을 정하고, 그 지점에서 각 사람까지의 거리의 합, 그 합이 최솟값이 되는 지점을 구하고 싶은 것이다. 대충 식으로 표현하면 다음과 같다. 한 지점을 x로 두고, 그 지점에서 각 사람까지의 거리의 합이 f(x)이다. 우리가 고등학교 수학에서 배웠듯이 이 f(x)의 값이 최소가 되는 지점은 무조건 X의 원소인 X[i]이다. 여기서 미분으로 경향성을 찾아도 되고 여러 가지 방법이 있지만, 제일 편한 방법은 그냥 1차 함수이니까 계수만 보면 된다. A[i]가 절반이 넘어가는 그 순간의 X[i]가 답이다... 2025. 1. 9. 백준 1456 거의 소수 C++ 간단한 해설 A와 B사이의 소수의 제곱수들을 구하면 된다. 이 때, A와 B가 10^14승까지 될 수 있어서 별 생각 없이 코드를 작성하다 보면 long long형의 범위를 초과할 수 있다. 1부터 10^14 사이의 제곱수들을 파악하면 되는 것이므로, 10^7까지의 소수만 계산하면 된다.[sqrt(10^14)] 그런데, 막상 A와 B 사이의 제곱수들을 파악할 때도 오버플로우가 발생할 수 있다. 다음과 같은 반례가 존재한다.입력1 100000000000000출력670121 현재 제곱수 값 x 소수 가 overflow될 수 있는 가능성이 있기에,B / 현재 제곱수 값 답 #include #include #include #include #define ll long longusing namespace std;.. 2025. 1. 8. 이전 1 2 3 4 ··· 7 다음
