본문 바로가기

분류 전체보기

Baekjoon 1806 부분합 2019. 11. 11. Link https://www.acmicpc.net/problem/1806 결과 2380 KB / 8 ms 언어 C++ 17 풀이 투포인터 + 길이 개념 문제 투포인터 개념을 안다면 크게 어려운 문제는 안되는 거 같다. 연속이라는 전제 조건이 붙는 순간 투포인터가 가능하다 라고 알려주는 문제 같다. 소스코드 #include using namespace std; const int MAX = 100000; int inputs[MAX]; int _min(const int a, const int b) { return b ^ ((a ^ b) & -(a < b)); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int res = 0; int n, m; ..
Baekjoon 2003 수들의 합 2 2019. 11. 11. Link https://www.acmicpc.net/problem/2003 결과 2028 KB / 0 ms 언어 C++17 풀이 투 포인터를 이용해 연속된 부분합을 빠르게 구하는 아이디어를 연습하는 문제 투 포인터를 이해하기에는 완벽한 문제가 아닌가 싶다. 소스코드 #include using namespace std; const int MAX = 10000; int inputs[MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int res = 0; int n, m; cin >> n >> m; for (int i = 0; i > inputs[i]; int left = 0, right = 0; int sum = 0..
Baekjoon 2096 내려가기 2019. 11. 11. Link https://www.acmicpc.net/problem/2096 결과 3160KB / 24ms 언어 C++17 풀이 문제 조건이 너무 명확하다 못가는 위치를 제외한 합의 최대값을 현개 값으로 잡으면된다. 다만 메모리제한이 4MB인 점을 생각해 모든 위치를 기억하는것이 아닌 현재와 이전 1개의 라인만 기억하는 배열을 만들면 된다. 소스코드 #include using namespace std; const int MAX = 100000; int input[MAX][3] = {}; int maxBuffer[2][3] = {}; int minBuffer[2][3] = {}; int _max(const int a, const int b) { return a ^ ((a ^ b) & -(a < b)); } ..
Baekjoon 2748 피보나치 수 2 2019. 11. 11. Link https://www.acmicpc.net/problem/2748 결과 1988KB/ 0 ms 언어 C++17 풀이 재귀가 아닌 피보나치 수를 연습하는 문제 이 문제까지는 연습이 아닌가 싶다. 소스코드 #include using namespace std; const int MAX = 90; long long dp[MAX + 1] = {0, 1}; int main() { ios_base::sync_with_stdio(false); cin.tie(0); for (int i = 2; i > n; cout
Baekjoon 1406 에디터 2019. 11. 11. Link https://www.acmicpc.net/problem/1406 결과 20732KB / 72ms 언어 C++ 17 풀이 연결리스트를 연습하기에는 적당한 문제인거 같다. 처음에는 head, tail같은 더미노드가 없이 풀어보려 했지만 구현 복잡도가 너무 올라갔다. 이 문제는 더미노드가 있는게 처음, 끝 위치에 대한 커서를 구현하기 쉽다. 연결리스트를 구현하는게 가장 어려운 문제가 아닐까 싶다. 소스코드 #include using namespace std; const int MAX = 10'0000; struct Node { Node* pre; Node* next; char val; Node() : pre(nullptr), next(nullptr) {} Node(char v) : pre(nullp..
Baekjoon 17357 자동차가 차주 김표준의 편을 들면? 2019. 11. 11. Link https://www.acmicpc.net/problem/17357 결과 1988KB / 172 ms 언어 C++ 17 풀이 투포인터 개념을 적용하면 쉽게 풀리는 문제 각 케이스 마다 합을 구한 후 표준 편차 공식을 적용시키면 편하다. 표준편차를 구하기 전 합만 할면 되기 때문에 합을 구하는 과정에서 투포인터를 적용한다. 생각보다 빠르게 돈다. 소스코드 #include using namespace std; const int MAX = 1000; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; int val[MAX] = {}; for (int i = 0; i > val[i]; for ..
Baekjoon 17358 복불복으로 지구 멸망 2019. 11. 11. Link https://www.acmicpc.net/problem/17358 결과 1988 KB / 0 ms 언어 C++ 17 풀이 규칙을 찾는 문제처럼 보이지만 단순히 경우의 수를 구하는 문제이다. n개의 포트중 2개씩 사용할 수 없게 한다면 다음번에 고를 수 있는건 n-2개가 된다. 그 점을 이용해 MOD로 나눈 나머지를 기억해 가며 정답을 갱신하면 된다. 소스코드 #include using namespace std; const long long MOD = 1e9 + 7; int main() { long long n; cin >> n; long long res = 1; while (n) { res *= n - 1; res %= MOD; n -= 2; } cout
Baekjoon 4948 베르트랑 공준 2019. 11. 11. Link https://www.acmicpc.net/problem/4948 결과 2544KB / 4 ms 언어 C++ 17 풀이 에라토스테네스의 체의 연장선 소수를 구하는게 중요한 문제 n이 123456 까지기 때문에 2부터 2n까지의 소수를 전부 구하면 된다. 소수를 구한 뒤 개수는 매 순간 반복문을 통해 구해도 문제가 없다. 소스코드 #include using namespace std; const int MAX = 50000; int prime[MAX]; int primeCount; void eratos() { const int max = 123456 * 2 * 2; bool check[max + 1] = {true, true}; for (int i = 2; i < max + 1; i++) { if ..

티스토리툴바