본문 바로가기

분류 전체보기

Baekjoon 11048 이동하기 2019. 11. 11. Link https://www.acmicpc.net/problem/11048 결과 9800 KB / 76 ms 언어 C++17 풀이 시작점 (0, 0)을 제외하고서 (x-1, y) , (x-1, y-1) , (x, y-1) 세군데 중 누적된 최고값을 가져온다. DP는 어렵다. 소스코드 #include using namespace std; const short MAX = 1000; int board[MAX][MAX]; int dp[MAX][MAX]; const int posX[] = { -1, 0, -1 }; const int posY[] = { 0, -1, -1 }; int max(const int& a, const int& b, const int& c) { if (a < b && c < b) retur..
Baekjoon 5525 IOIOI 2019. 11. 11. Link https://www.acmicpc.net/problem/5525 결과 2844KB / 12 ms 언어 C++ 17 풀이 Hash를 이용하여 문제를 해결 string을 이용한 방법으로도 해결 가능할 듯 보인다. I를 1 O를 0인 2진수로 생각해 해시를 구성한다. 매 순간 특정 지점에서 해시를 구하면 string과 같은 복잡도가 나오거나 더 나오기 때문에 슬라이딩 윈도우처럼 값을 빼고 더하면서 해시를 구하면 O(n) 시간에 해시를 구할 수 있다. 비교할 해시랑 매 순간 구해지는 해시를 비교하면서 일치하는 개수를 구하면 된다. 소스코드 #include using namespace std; const int MAX = 1000000; const int MOD = 100000007; int targe..
Baekjoon 2164 카드 2 2019. 11. 11. Link https://www.acmicpc.net/problem/2164 결과 4124KB / 4ms 언어 C++71 풀이 전형적인 시뮬레이션 문제 사간제한도 2초에 n도 최대 20만밖에 안된다. n까지 모든 값을 queue에 넣고 1개가 될 때 까지 무한 반복하면 된다. 소스코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; queue q; for (int i = 1; i 1) { q.pop(); q.push(q.front()); q.pop(); } cout
Baekjoon 1654 랜선자르기 2019. 11. 11. Link https://www.acmicpc.net/problem/1654 결과 2148 KB / 4ms 언어 C++ 17 풀이 이분탐색을 이용해 정답을 유도하는 과정 초기 범위를 1 ~ 최대값으로 설정하고 최대 랜선 길이를 구하는 함수를 통해 구분을 한다. 기준 값은 현재까지의 최대 값을 기준으로 left와 right를 구분한다. 소스코드 #include #include #include using namespace std; int getMax(vector input) { int res = 0; for (unsigned int i = 0; i < input.size(); i++) if (res < input[i]) res = input[i]; return res; } long long getMax(lon..
Baekjoon 3908 서로 다른 소수의 합 2019. 11. 11. Link https://www.acmicpc.net/problem/3908 결과 2052 KB / 0 ms 언어 C++ 17 풀이 에라토스테네스의 체를 이용해 소수를 먼저 구한다. [선택된 개수][1120보다 죽은 수]를 저장하는 O(kn) DP를 구한다. 입력되는 값에 대하셔 해당 위치의 값을 출력한다. 소스코드 #include #include using namespace std; vector primes; const short MAX = 1120; const short PRIME_MAX = 187; const short SELECT_MAX = 14; int prime_dp[SELECT_MAX + 1][MAX + 1]; void find_prime() { bool prime[MAX + 1] = { tr..
Baekjoon 3896 소수 사이 수열 2019. 11. 11. Link https://www.acmicpc.net/problem/3896 결과 4152 KB / 24 ms 언어 C++17 풀이 최대 값이 1299709로 충분히 배열로 만들만 하다 입력값을 기준으로 조건을 걸어서 소수라면 0을 합성수라면 1 ~ 합성수까지의 개수를 구하면 된다. 매번 결과를 구해도 될만큼 테스트 케이스가 많지 않기 때문에 매 순간 돌려도 된다. 해당 수가 소수인지 아닌지를 판별하는 방법은 에라토스테네스 체를 구하는 과정의 배열을 재 사용하도록 한다. 소스코드 #include #include using namespace std; const int MAX = 1299709; bool prime[MAX + 1] = { true, true }; vector primes; void eratos..
Baekjoon 2512 예산 2019. 11. 11. Link https://www.acmicpc.net/problem/2512 결과 2148 KB / 0 ms 출처 BOJ 언어 C++ 17 풀이 이분탐색에 기반한 문제 풀이 0 ~ 최대값 사이에서 이분탐색을 진행하며 조건에 맞는 값을 계산한다. 입력된 총 예산을 기준으로 범위를 수정해가며 이분탐색이 종료될까지 진행한다. 소스코드 #include #include using namespace std; int getMax(vector inputs) { int res = 0; for (int i = 0; i < inputs.size(); i++) if (res < inputs[i]) res = inputs[i]; return res; } int getSum (vector inputs, int mxm) { int ..
Baekjoon 1929 소수 구하기 2019. 8. 23. Link https://www.acmicpc.net/problem/1929 소스결과 2884 KB / 16 ms 출처 Baekjoon 언어 C++ 17 분류 에라토스테네스의 체 설명 입력된 범위 내에 있는 소수를 전부 출력하자 최대 범위가 100만이다. 시작 값이 소수인지를 확인하면 절대 시간내에 해결이 안된다. 에라토스테네스의 체를 이용해 100만까지 구한 후 소수를 따로 저장하면 된다. 알고리즘 1. 에라토스테네스의 체를 이용해 소수만 저장한다. 2. 저장된 소수를 처음부터 탐색한다. 3. 범위 내에 들어가면 출력하고 범위를 벗어나면 출력을 종료한다. 소스코드 #include using namespace std; const int MAX = 1000000; void eratos(bool arr[MAX..

티스토리툴바