알고리즘55 백준 7490 0 만들기 C++ 간단한 해설n이 최대 9까지이고, 경우의 수가 공백, +, -의 3가지이므로, 연산자를 고르는 경우의 수는 3^8개이다.브루트포스를 해서 전부 세보자. 그런데 C++로 하면 파싱에 어려움을 겪을 수 있다. C++에서 파싱은 기본적으로 노가다이다.(설명을 위해 공백도 연산자라 하자.)나의 경우, 연산자를 고르고 연산자가 공백인 경우, 공백이 존재하는 문자열과 없는 문자열 2개를 만든다.정답을 출력할 경우 공백이 존재하는 문자열을 사용하여 출력하고, 그게 아니면 공백이 존재하지 않는 문자열로 파싱을 한다. 공백이 존재하지 않는 문자열을 이용하여 파싱할 때, 일단 연산자의 위치를 배열에 저장한다.그리고 연산자의 위치를 토대로 stoi()를 적절히 이용하면 된다. 답#include #include #inclu.. 2024. 11. 29. 백준 1450 냅색문제 C++ 간단한 해설 이전 포스팅과 비슷하게 2^30의 경우의 수이므로 meet in middle러 2^15, 2^15로 나눈다. 기존 논지는 이전 포스팅과 비슷하다. 백준 1208 부분수열의 합 2 C++간단한 해설 meet in middle을 활용하면 된다. 중간에서 만나기를 활용하지 않을 경우, n이 최대 40이라서 부분 수열의 개수가 2^40의 경우가 나오게 된다. 그러나, 중간에서 만나기를 활용하는 경우ash9river.tistory.com ll rightIdx=upper_bound(rightPartialSum.begin(),rightPartialSum.end(),limitVal)-rightPartialSum.begin();ans+=rightIdx; c- 왼쪽 부분수열의 값을 target으로한 upper.. 2024. 11. 25. 백준 1208 부분수열의 합 2 C++ 간단한 해설 meet in middle을 활용하면 된다. 중간에서 만나기를 활용하지 않을 경우, n이 최대 40이라서 부분 수열의 개수가 2^40의 경우가 나오게 된다. 그러나, 중간에서 만나기를 활용하는 경우 왼쪽 부분 수열 2^20, 오른쪽 부분 수열 2^20, 총 부분 수열의 개수는 2*2^20=2^21이다. 왼쪽 부분 수열 합 배열을 만들고, 그 배열에서 값을 선택하고 오른쪽 부분 수열에서 (S - 값)을 구하면 된다.물론 왼쪽에서만 S가 나올 수 있고, 오른쪽에서만 S가 나올 수 있다. 반례는 다음과 같다. 4 10 0 0 1answer: 84 00 0 0 0answer: 1540 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.. 2024. 11. 25. 백준 7453 합이 0인 네 정수 C++ 간단한 해설 시간제한이 12초이니까, a+b와 c+d로 나누어서 이진탐색을 활용하면 된다. 입력이 a[0] b[0] c[0] d[0]a[1] b[1] c[1] d[2]...이런식으로 주어지는 것에만 유의 답#include #include #include #include #define ll long longusing namespace std;vector> v;vector a;vector b;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n; cin>>n; v.resize(4,vector(n)); for(int i=0;i>v[j][i]; } } for(int i=0;i 2024. 11. 18. 백준 13164 행복 유치원 C++ 간단한 해설 다음과 같은 문제에서는 조를 k개의 조로 나누고, 그 조의 최댓값과 최솟값의 차가 비용이다.그리고 그 차의 합이 최소가 되는 값을 구해야 한다. 그러면 우리가 그 값을 어떻게 생각해야할까? 5 31 3 5 6 10다음과 같이 값이 주어졌다고 생각해보자. 그러면 당연히 5와 6을 묶고, 그리고 제일 차이가 적어보이는 3이랑 묶어서 1 / 3 5 6 / 10 또는, 1 3 / 5 6 / 10 이런 두 가지 경우의 수가 나올 것이다. 여기서 지목해야 하는 것은 값의 차이이다. 값의 차이를 기준으로 묶으면 된다.그러면 값의 차이를 기준으로 입력값을 다음과 같이 나타낼 수 있다. // 이전1 3 5 6 10// 이후 2 2 1 4 이렇게보니까 뭔가 감이 잡힌다.아까 내가 임의로 선택한 방식이 어떤 .. 2024. 11. 18. 백준 1990 소수인팰린드롬 C++ 간단한 해설 범위가 5~100,000,000이므로 최대 1억까지의 정수를 탐색한다. O(n) 정도면 얼추 된다는 뜻이다. 일단 에라토스테네스의 체를 이용해서 소수를 판별한다. 그리고 범위 안의 소수인 수들만 팰린드롬 판별을 하면 된다. 팰린드롬 판별은 수를 문자열로 변환하고, reverse() 메서드를 이용해서 간단하게 비교하면 된다. 답 #include #include #include #include #define ll long longusing namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); ll a,b; cin>>a>>b; vector v(b+1,true); v[0]=v[1]=false; for(ll i=2;i ans; for.. 2024. 11. 14. 이전 1 2 3 4 5 6 ··· 10 다음
