[백준]/C++

https://www.acmicpc.net/problem/24041  #문제 간단 정리이분탐색(매개변수 탐색) #문제 해결 방법 범위 관리를 잘 해줘야 되는 문제 같다 우선 x가 범위가 매우 넓으니  매개변수 탐색으로 logn 을 사용하고 각각 세균의 개수를 확인하면 O(n) 인데정렬을 한 후에 최대 k개를 총합에서 제거한다고 생각하면n log n 이라 이분탐색 + 정렬이라log n * nlogn 정도로 생각 할 수 있는데 세균의 범위는 대략 2e9 (20억 정도)각 n의 s*max(1,x-L) 합 최악의 경우 N=1 G=1e9 , S:1, L 1e9로S * max(1, x - L) 1 * (x - 1e9) x - 1e9 x x의 범위는 2e9이다 n의 범위는 20만이니 시간복잡도는 충분하다  #전체 코..

https://www.acmicpc.net/problem/10975 #문제 간단 정리 구현 + 그리디라고 볼 수 있다.  #문제 해결 방법 우선 문제를 읽고 각 입력으로 숫자가 주어졌을 때 덱을 어떻게 최소한으로 써야되는지 알아내는 문제이다 우선 입력은 3 6 0 9 5 4 이렇게 주어지고 이 숫자들을 정렬했을 때는0 3 4 5 6 9 임을 알 수 있는데 여기서 처음에 주어지는 3과 6을 보면 0 3 4 | 5 6 9 이렇게 각자 절반에 절반씩 띄워진 숫자라는 걸 알 수 있다. 여기서 만약에 입력이 다르게 온다고 생각을 해보면 예를 들어서 0 3 4 5 6 9 로 주어진다고 생각해보면 정렬했을때도 연속되기 때문에 하나의 덱에 앞뒤로 값을 넣으면 되기 때문에 당연히 덱을 하나 더 만들 필요가 없다는 걸 알..

https://www.acmicpc.net/problem/21738  #문제 간단 정리 bfs 문제 #문제 해결 방법 우선 문제를 잘 이해해 보면펭귄이 이어진 지지대가 2개 는 있어야 된다 -> 즉 펭귄과 지지대를 잇는 경로만 멀쩡히 있으면 된다-> 즉 가장 가까운 지지대 2개를 골라서 그 지지대 경로를 제외한 모든 얼음을 깨면 된다-> 가장 가까운 지지대 2개를 bfs 를 이용해서 찾는다 라는 발상이 가능하다중요한건 dfs 를 처음에 사용하려 했는데 가장 가까운 지지대 경로 를 찾아야해서 부적합 하기 때문에 bfs 를 사용했고 ,( 재귀형식으로 만드는ㄴ게 불가능하진 않겠지만 귀찮을 것이다) 그리고 결국 가장 가까운 거리의 2개의 지지대 경로만 찾으면 되기 때문에2개를 찾자마자 바로 결과를 출력했다.딱히..

https://www.acmicpc.net/problem/2563#include #include #include using namespace std;int a, b;int n;vector> paper;void fill() { for (int i = 0; i > n; paper.resize(260, vector(260)); while (n--) { cin >> a >> b; fill(); } int ans = 0; for (int i = 0; i

https://www.acmicpc.net/problem/15925  #문제 간단 정리구현 + 브루트 포스 문제 #문제 해결 방법우선 브루트포스로 문제를 풀리게하도록 고심한 흔적이 여럿 보이는데  문제의 n 이 31 까지로 상당히 작고 보드가 홀수로만 주어진다는 점이 주목할만한 점인데 만약 행이나 열을 1 이나 0으로 바꾸게 되면 항상 1이나 0이 늘어나기 때문에 다음에 더 유리한 조건이 된다 때문에 행과 열을 반복해서 교차로 키거나 끌 수 있는지 확인해주면 (N^2) 한번 키거나 끌 때 N개의 컴퓨터가 바뀌니까  이 작업이 최대 N 번복 N^2 * N 해서 대략 N^3 정도인 듯 하다 나머지는 개인의 구현 역량에 따라 구현하면 된다. #전체 코드#include #include #include using..

https://www.acmicpc.net/problem/17088  #문제 간단 정리수학 + 브루트 포스 문 #문제 해결 방법 등차수열이기 때문에 결국에는 첫항과 마지막항에 +1 0 -1 을 하면 공차가 각각 정해지는데 이렇게 3*3 경우의 수로 공차가 정해지면 각 항에서 start + 공차 * 인덱스 를 한 값이 각 벡터에 올바르게 들어 갈 수 있는지 체크해주면 (+1 -1 을 해서 값을 만들 수 있는지 ) 확인해 주면 된다  #전체 코드#include #include #include using namespace std;int n;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; vector vec(n);..

https://www.acmicpc.net/problem/30023  #문제 간단 정리 그리디 + 문자열 + 구현 정도로 볼 수 있는 문제  #문제 해결 방법 일단 모든 색을 같게 맞추는데 있어서 우선 앞에서부터 하나씩 맞춰간다고 생각 할 수 있다.이런 경우에는 맨 앞의 색이 3가지색으로 고정되고그 앞에 색에 맞춰서 나머지 색깔을 맞춰주면 된다. 이 사고의 흐름은 모든 3가지 연속된걸 바꿔보는 건 너무 많기 때문에자연스럽게 하나씩 앞에서부터 맞춰본다는 생각이 드는게 맞는 것 같다  그렇게 마지막 -2 개 까지 맞춰놓고 마지막 2개도 같은색인지 확인해 주면 되는데 여기서 문자열 바꾸는걸 문자열 함수로 바꿔주게되면 문자열 바꾸는데 n의 시간복잡도가걸리기 때문에 배열로 처리해주는게 좋다그래서 처음엔 문자열 함..

https://www.acmicpc.net/problem/14503  #문제 간단 정리 전형적인 구현 , 시뮬레이션 문제라고 할 수 있다. #문제 해결 방법 중요한건 우리가 뭘 구현해야될지 순서를 잘 생각하고 분할해야된다특히 특정 흐름을 생각하면서 함수로 분할하는게 매우 도움이 된다 이 문제 같은 경우에는 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,반시계 방향으로 90도회전한다.바라보는 방향을 기준으로 앞쪽 칸이 청소되지 ..

https://www.acmicpc.net/problem/18114    #문제 간단 정리 투 포인터로 풀었다  #문제 해결 방법  1개로 되는지 확인하고2개로되는지확인3개로되는지 확인한다 2개로 되는지 확인하는 경우는 전형적인 투포인터로 사용하고 3개로되는경우는i번째 를 선택한 다음에다른 2개를 투포인터로 조건에 맞도록 탐색한다 #전체 코드#include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, C; cin >> N >> C; vector vec(N); for (int i = 0; i > vec[i]; sort(vec.begin(), vec.end())..

https://www.acmicpc.net/problem/12924  #문제 간단 정리 문자열을 사용한 구현문제정도 #문제 해결 방법 다른사람들은 어떻게 풀었을지 모르겠지만 일단 문제에서 주어진거처럼 뒤에서 1~ 문자열 길이 만큼 잘라서앞으로 붙여서 B 보다 작다면 ok 라는 방식으로 직관적으로 구현햇다 대략 길이가 7자리수니까 주어진 범위가 이백만 정도니까 이백만 x 7 해도 문제가 없음을 알 수 있다.  #전체 코드#include #include #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); string sA, sB; cin >> s..